Recursion Notes

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. It continues calling itself until it reaches a base case.

Key Components of Recursion

1. Base Case: The condition that stops recursion.
2. Recursive Case: The function calls itself with a modified parameter moving toward the base case.

Example: Factorial of a Number

# Recursive function for factorial

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # Output: 120

How it Works?

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 (Base Case)

Types of Recursion

1. Direct Recursion

A function directly calls itself.

def direct_rec(n):
    if n == 0:
        return
    print(n)
    direct_rec(n - 1)

2. Indirect Recursion

A function calls another function, which then calls the first function.

def A(n):
    if n > 0:
        print(n, end=' ')
        B(n - 1)

def B(n):
    if n > 1:
        A(n // 2)

A(10)  # Output: 10 9 4 3 1

3. Tail Recursion (Optimizable in some languages, but not in Python)

def tail_rec(n, result=1):
    if n == 0:
        return result
    return tail_rec(n - 1, result * n)

4. Tree Recursion (A function calls itself more than once)

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

5. Nested Recursion

def nested_rec(n):
    if n > 100:
        return n - 10
    return nested_rec(nested_rec(n + 11))

Final Thoughts

• Always define a base case to avoid infinite recursion.
• Optimize recursive functions using memoization or dynamic programming.
• Be cautious with Python’s recursion limit and stack usage.
• Iterative solutions are usually more memory-efficient than recursive ones in Python.

🚀 Master these recursion concepts and practice FAANG-level problems to excel in interviews!