Analyze Recursive Functions

The time complexity for recursive functions is the product between:

1. The number of times the recursive function is called.
2. The time complexity per call.

For the former, we can get help from the State Space, whereas for the latter we can simply use the technique I explained before.

The Space Tree

Based on the function we are examining, we can derive the space tree to understand the total number of calls.

Let's look at this example:

from typing import List


def print_list(lst: List[int]) -> None:
    if not lst:
        return

    print(lst[0])
    print_list(lst[1:])


lst = [1, 2, 3]
print_list(lst)

Which would give us the following space tree:

As you can see, the number of nodes is proportional to the size of the input list, which is $n$. Therefore, the function will be called $n$ times (point 1) and the time complexity per call is $1$ (point 2). In fact, we are simply printing a value, nothing else. So, the final time complexity will be the product of such value, which is $O(n)$.

Regarding the space complexity, we can use the Space Tree again, which results in $n$ frames in the Call Stack, so the space complexity is $O(n)$.

Other Examples

Fibonacci

A naive implementation of the Fibonacci sequence could be something like:

def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1

    return fib(n - 1) + fib(n - 2)


print(fib(4))

This would give us the following space tree:

We start from level 0 with 1 node, then level 1 with 2 nodes, level 2 with 4 nodes - in general, $2^k$ nodes for the $k$ level. So the time complexity will be $O(2^k)$.

Regarding the space, the maximum number of frames we would have is proportional to the height of the tree, which is at most $n$. Hence, $O(n)$.

In fact, if we mark the nodes that would be in the call stack until we reach the first base case, we would have the following space tree: