Amount of times method is called in recursion

Question

This is kind of a basic question, but its busting my head and I cant seem to grasp it. I know that when a recursive function (e.g: rec(int n)) is called recursively twice:

rec(int n):
    if n > 1:
        rec(n-1)
        rec(n-1)

The amount of times the method will be called will be $2^n - 1$. However, how can one find a general 'formula' for recursive methods with $3$ recursive calls in the code body? or $4$? or $5$? or $N$?

Answer 1

Imagine that your calls form a tree (growing downwards, with the root as the topmost level) with the root being rec(n) (level $0$ in the tree), then $N$ nodes containing each a call rec(n-1) (level $1$ in the tree), then each of these $N$ nodes will have $N$ nodes (each containing a call rec(n-2), all of them forming level $2$ in the tree) and so on. In general the calls rec(n-k) will populate level $k$.

Note that on level $0$ you have $1$ call; on level $1$, $N$ calls; on level $2$ you will have $N \cdot N = N^2$ calls (because on level $1$ there were $N$ nodes, and each of them again has $N$ nodes), on level $k$ there will be $N^k$ (induction!).

What is the bottom of this tree? If you really meant your condition to be the strict inequality n>1 then you stop at $n=2$, which means level $n-2$, filled with $N^{n-2}$ copies of rec(1).

Counting all these nodes (which represent calls) you get $1 + N + N^2 + \cdots + N^{n-2}$, which is seen to be a geometric progression, which has a well-known sum: $\dfrac {N^{n-1} - 1} {N - 1}$.

If your inequality is not strict (i.e. n >= 1), then you stop at $n=1$, which is on the level $n-1$, filled with $N^{n-1}$ copies of rec(0), so the number of calls will be $\dfrac {N^n - 1} {N - 1}$. Since when you take $N=2$ you find the formula that you yourself give, I suspect that there should have been a non-strict inequality in your code snippet.