Understanding Recursive Function Complexity in Algorithms

In this section, we’ll explore how to analyze the complexity of recursive functions, a topic often perceived as challenging, but highly important in computer science.

To determine the complexity of a recursive function, we follow these general steps:

Compute the complexity of a single recursive call.
Count the total number of recursive calls as a function of input size.
Multiply the number of calls by the single call complexity.

Example 1: A Simple Recursive Chain

Consider the following function:

def foo(n):
    if n == 1:
        return
    foo(n - 1)

Here’s how to evaluate its complexity:

The body of the function does not depend on n, so: $\text{Single call complexity} = \mathcal{O}(1)$
Let’s draw the recursive call chain for $n = 4$ :

foo(4)
  └── foo(3)
        └── foo(2)
              └── foo(1)

As we see, there are $n$ recursive calls. Therefore:

$\text{Total calls} = n$
$T(n) = \mathcal{O}(1) \times n = \mathcal{O}(n)$

Example 2: A Recursive Tree with Multiple Calls

Now consider a slightly different function:

def bar(n):
    if n == 1:
        return
    bar(n - 1)
    bar(n - 1)

Again, the body doesn’t depend on $n$ , so:

$\text{Single call complexity} = \mathcal{O}(1)$

Let’s analyze the recursive call tree for $n = 4$ :

bar(4)
├── bar(3)
│   ├── bar(2)
│   │   ├── bar(1)
│   │   └── bar(1)
│   └── bar(2)
│       ├── bar(1)
│       └── bar(1)
└── bar(3)
    ├── bar(2)
    │   ├── bar(1)
    │   └── bar(1)
    └── bar(2)
        ├── bar(1)
        └── bar(1)

This forms a binary tree, where each node creates 2 recursive calls.

Let’s compute the number of nodes in this tree:

Level 0 has $2^0 = 1$ node
Level 1 has $2^1 = 2$ nodes
Level 2 has $2^2 = 4$ nodes
Level 3 has $2^3 = 8$ nodes

So the total number of calls is:

$1 + 2 + 4 + 8 = 2^4 - 1 = 15$

In general, for $n$ levels:

$\text{Total recursive calls} = 2^n - 1$

Thus, total complexity:

$T(n) = \mathcal{O}(1) \times (2^n - 1) = \mathcal{O}(2^n)$

General Formula for Recursive Tree Complexity

Let:

$C$ be the number of recursive calls per invocation
$L$ be the number of levels in the recursive call tree
$S$ be the complexity of a single call

Then the total complexity is:

$T(n) = \mathcal{O}(S \times C^L)$

From the previous example:

$C = 2$
$L = n$
$S = \mathcal{O}(1)$

So:

$T(n) = \mathcal{O}(1 \times 2^n) = \mathcal{O}(2^n)$

What Determines the Number of Levels?

To determine $L$ , observe:

Initial value of the recursive parameter — typically $n$
Step size — e.g., $n - 1$ per call
Base case termination — e.g., $n = 1$

If the recursion goes from $n$ to $1$ with a step of $-1$ , then:

$L = n$

Applying the Formula: Final Example

def baz(n):
    if n == 1:
        return
    baz(n - 1)
    baz(n - 1)

We identify:

Single call complexity: $\mathcal{O}(1)$
Number of recursive calls: $2$
Number of levels: $n$

Using the formula:

$T(n) = \mathcal{O}(1 \times 2^n) = \mathcal{O}(2^n)$

Important Observations

When the number of recursive calls per level is $1$ , it forms a chain, and the total complexity is:

$\mathcal{O}(n)$

If recursion occurs inside a loop, complexity analysis depends on the loop structure.

Summary of Recursive Complexity Formula

For most recursive functions with tree structure:

$T(n) = \mathcal{O}(\text{Single Call Complexity}) \times \mathcal{O}(\text{Calls per node})^{\text{Levels}}$

This formula is widely applicable but assumes:

Fixed number of recursive calls per invocation
No loop-based dynamic recursion count