Recursion Basics

# CHAPTER 6

Recursion Basics #

1. Introduction #

2. Learning Objectives #

• Define what a recursive function is.

• Understand the critical importance of a Base Case.

• Visualize how the OS Call Stack manages recursive memory.

• Analyze the hidden Space Complexity dangers of Recursion.

3. The Anatomy of Recursion #

1. 1. The Base Case: The absolute simplest, smallest scenario that can be solved instantly without recursion. It tells the function to STOP calling itself.

1. 2. The Recursive Case: The part of the code where the function calls itself, passing in a slightly *smaller* or *simpler* piece of data.

4. A Classic Example: Factorials #

# Python Example: Recursive Factorial
def factorial(n):
    # 1. The Base Case (The Stopping Point)
    if n <= 1:
        return 1
        
    # 2. The Recursive Case (Calling itself with smaller data)
    return n * factorial(n - 1)

print(factorial(5)) # Outputs 120

5. The OS Call Stack (How Memory Works) #

When we run factorial(3):

1. 1. factorial(3) runs. It pauses and waits for factorial(2) to finish. The OS pushes this paused state onto the Stack.

1. 2. factorial(2) runs. It pauses and waits for factorial(1) to finish. Stack grows.

1. 3. factorial(1) runs. Base Case hit! It returns 1 instantly.

1. 4. factorial(2) wakes up, calculates 2 * 1 = 2, and returns 2.

1. 5. factorial(3) wakes up, calculates 3 * 2 = 6, and returns 6.

Visualizing the Call Stack:

[ factorial(1) ] <-- Returns 1
[ factorial(2) ] <-- Waiting for factorial(1)
[ factorial(3) ] <-- Waiting for factorial(2)
-----------------
   MAIN PROGRAM

6. The Danger: Stack Overflow #

7. Time and Space Complexity #

• Time Complexity: Usually O(n). For factorial(5), the function is called 5 times.

• Space Complexity (The Hidden Cost): Unlike a simple for loop, Recursion is computationally expensive. Because every recursive call is pushed onto the OS Call Stack, n recursive calls take up O(n) Space Complexity. A standard for loop only takes O(1) space!

8. Mini Project: Fibonacci Sequence #

// Java Example: Recursive Fibonacci
public class RecursionProject {
    
    public static int fibonacci(int n) {
        // Base Cases
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // Recursive Case (Branching into TWO calls!)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci at position 6 is: " + fibonacci(6));
    }
}

*Warning: The Recursive Fibonacci creates a massive "Tree" of function calls, resulting in a horrifying O(2^n) Time Complexity. We will fix this using Dynamic Programming in Chapter 28.*

9. Common Mistakes #

• Missing return statements: A beginner might write factorial(n-1) instead of return n * factorial(n-1). The data must be returned backward down the call stack, or the final result is lost.

10. Best Practices #

• Iterative vs Recursive: Anything that can be written recursively can also be written iteratively (using a while loop). If an algorithm requires 10,000 deep steps, a while loop is safer to avoid Stack Overflows. Recursion should be saved for Non-Linear data structures (like Trees and Graphs) where traversing branches with loops becomes overwhelmingly complex.

11. Exercises #

1. 1. Write a recursive function to sum all numbers from 1 to n.

1. 2. Draw a Call Stack diagram by hand showing exactly what happens in memory when sum(4) is executed.

12. MCQs with Answers #

13. Interview Preparation #

• *Core Mechanics:* "Explain the architectural difference between Iteration and Recursion. Analyze the exact Time and Space Complexity tradeoffs between a while loop summing an array versus a Recursive function summing the same array."

• *Algorithmic Pattern:* "Write a recursive function to reverse a string." *(Hint: Take the first character, recursively call the function on the rest of the string, and append the first character to the very end of the returning result).*

Common Pitfalls:

• In whiteboard interviews, candidates often forget the return keyword in the Recursive Case. If you write factorial(n-1) instead of return n * factorial(n-1), the recursion works, but the final answer is completely lost in the stack and returns null.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #