What is Recursion?
Recursion is a fundamental programming concept where a function solves a problem by calling itself with a smaller or simpler version of the same problem. This section breaks down the two essential parts of any recursive solution.
The Base Case
This is the terminating condition. It's the simplest version of the problem that can be solved directly, without making another recursive call. Without a base case, a recursive function would call itself forever, leading to a "Stack Overflow" error.
The Recursive Case
This is where the function calls itself, but with a modified argument that moves it closer to the base case. It breaks the problem down into a smaller piece and combines its result with the solution from the recursive call.
Core Theory Q&A
These are the most common theory questions you'll encounter. Click on any question to reveal the answer. This is a great way to test your understanding of the key concepts.
Recursion vs. Iteration
Understanding the differences between recursion and iteration (using loops like `for` or `while`) is a classic exam topic. Both can solve the same problems, but they have different trade-offs.
| Aspect | Recursion | Iteration |
|---|---|---|
| Mechanism | Function calls itself. | A loop (e.g., `for`, `while`) repeats a block of code. |
| Termination | Ends when the base case is reached. | Ends when the loop condition becomes false. |
| Memory Usage | Uses the call stack. Can be memory-intensive (risk of Stack Overflow). | Uses constant memory (for loop variables). More memory-efficient. |
| Code Length | Often shorter and more elegant for problems that are naturally recursive (e.g., tree traversal). | Often longer and more complex, requiring manual state management. |
| Performance | Generally slower due to the overhead of function calls. | Generally faster as there is no function call overhead. |
How it Works: The Call Stack
Recursion relies on the "call stack" to keep track of all the function calls. When a function is called, it's "pushed" onto the stack. When it returns, it's "popped" off. Let's visualize this with `factorial(3)`.
Call Stack
Explanation:
Click the button to start the animation and see how the call stack works step-by-step.
Programming Problem Explorer
This is the best way to prepare for the programming part of the exam. Select a problem to see its solution, a detailed explanation of the logic, and an interactive "Try It Out" panel to test your understanding.
Select a Problem:
Java Solution:
Logic Explanation: