Recursion Basics
A function that calls itself to solve smaller instances of the same problem.
Input (N): 5
Ready to visualize recursion.
Stack Empty
Intuition
Recursion is solving a problem by breaking it down into smaller versions of itself. It's like looking into parallel mirrors!
Concept
- Base Case: The condition to stop recursion (e.g., n=1). Without this, you get infinite recursion (Stack Overflow).
- Recursive Case: The part where the function calls itself with a smaller input.
- Call Stack: The computer uses a stack to keep track of function calls.
How it Works
Factorial(n): n * factorial(n-1)
Fibonacci(n): fib(n-1) + fib(n-2)
Notice how Fibonacci creates a tree of calls, often recalculating the same values (overlapping subproblems). This is why simple recursion can be slow (O(2^n))!
Step-by-Step Breakdown
Watch the visualization:
- Factorial: Linear stack growth O(N).
- Fibonacci: Exponential tree growth O(2^N).
When to Use
- Tree/Graph traversals (DFS).
- Divide and Conquer algorithms (Merge Sort, Quick Sort).
- When the problem has a recursive structure.
When NOT to Use
- When stack space is limited (risk of overflow).
- When simple iteration is much more efficient.
How to Identify
"Compute nth...", "Tree structure", "Subproblems".
Frequently Asked Questions
What is Recursion Basics?
A function that calls itself to solve smaller instances of the same problem.
What is the time complexity of Recursion Basics?
The time complexity is: Best case varies, Average case Varies, Worst case varies. Space complexity is varies.