Kaushik's Notes

Recursion

2 min read

Recursion in Python

Types of Recursion

  • Direct Recursion: Function calls itself directly.
  • Indirect Recursion: Function calls another function which in turn calls the original function.
  • Tail Recursion: Recursive call is the last operation in the function (not optimized in Python).
  • Head Recursion: Recursive call is the first operation in the function.
  • Tree Recursion: Function calls itself more than once per call (e.g., Fibonacci).

Detailed Notes

  • Recursion is a method of solving a problem where the solution depends on solving smaller instances of the same problem.
  • A recursive function calls itself until it reaches a base case, which stops the recursion.
  • Every recursive function must have:
    • Base Case: Condition that ends recursion.
    • Recursive Case: The function calls itself with a modified argument.

Basic Recursive Function Example

def factorial(n):
    if n == 0:  # base case
        return 1
    else:
        return n * factorial(n - 1)  # recursive call

Visual Flow for

factorial(3)

factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * (1 * factorial(0)))
→ 3 * 2 * 1 * 1 = 6

Fibonacci Series (Tree Recursion)

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

Indirect Recursion Example

def funcA(x):
    if x > 0:
        print("A", x)
        funcB(x - 1)
 
def funcB(x):
    if x > 0:
        print("B", x)
        funcA(x // 2)
 
funcA(5)

Key Points

  • Recursion is elegant but may cause performance issues if not handled properly.
  • Python has a recursion limit (default: 1000), set using sys.setrecursionlimit(limit).
  • Recursive solutions are often easier to write for problems like tree traversal, factorial, Fibonacci, etc.
  • Every recursion can be rewritten iteratively.

Advance Tips and Best Practices

  • Always define a base case to avoid infinite recursion.
  • Use memoization to optimize overlapping subproblems (e.g., in Fibonacci).
# Memoization example
memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
  • Tail recursion is not optimized in Python due to lack of tail-call optimization.
  • Avoid deep recursion for large input sizes — use iteration instead or increase the recursion depth carefully.
  • Debugging recursion can be tricky; use print statements or visualizers to trace.

Relevant Images

Recursive Function Structure

Fibonacci Recursion Tree

Stack Representation in Recursion

References

Graph View

Backlinks