Recursive Functions

Understanding Recursion

At their core, recursive functions solve a problem by calling themselves with smaller portions of the input. They typically have:

  • Base Case: A simple scenario where the answer is directly known, stopping the chain of calls.
  • Recursive Case: Where the function calls itself with a reduced version of the problem.

Time Complexity

To determine the time complexity of a recursive function, consider:

  1. Number of Recursive Calls: How many times does the function call itself? This is often visualized as a "recursion tree" where each node is a function call.
  2. Work Done Per Call: What operations are performed within a single function call, aside from the recursive call itself?

Example: Factorial Calculation

Here, the factorial function makes n recursive calls. The work done in each call (excluding recursion) is a single multiplication. This leads to a time complexity of O(n).

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

 

Space Complexity

The space complexity of a recursive function is primarily determined by the depth of the recursion. Why? Here's how memory is used:

  • Function Call Stack: Each time a function calls itself, its state (local variables, return address) needs to be stored on the call stack so it can be resumed later.
  • Maximum Depth: The deepest your recursion goes determines the maximum size of this stack.

Example: Fibonacci Sequence

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

This has a significantly worse space complexity than factorial. Each call branches into two recursive calls, so the recursion depth can be as large as n. This tends toward a space complexity of O(n).

Important Considerations

  • Not All Recursion is Linear: Some recursive algorithms have branching factors larger than one, leading to exponential time complexities.
  • Optimization Techniques: Tail recursion and memoization (storing previously computed results) can sometimes be used to improve the efficiency of recursive functions.