Recursion formulas

For a function that makes exactly one recursive call, on $n-1$, and stops at n == 0 without a further call (for example, a factorial with base case n == 0). $C(n)$ counts the initial call and the base-case call. If the base case is at n == 1 instead (with $n\ge 1$), the count is $n$. Always check where the base case fires.

For a function that makes one recursive call on n / 2 (integer division) and stops at n == 0, like bin above. The calls that print or do work (those with $n\ge 1$) number $\lfloor {\log }_{2}n\rfloor +1$, which is the number of bits of $n$. The extra call is the base case n == 0.

For a function with base cases n == 0 and n == 1 that makes no further calls, and otherwise calls itself on $n-1$ and $n-2$. The $+1$ counts the current call. $F_k$ is the standard Fibonacci sequence $F_0=0,F_1=1,F_k=F_{k-1}+F_{k-2}$. Of the $2F_{n+1}-1$ calls, $F_{n+1}$ are base-case calls (leaves) and $F_{n+1}-1$ make further calls. The count grows as $\Theta ({\phi }^n)$, where $\phi =(1+\sqrt{5})/2\approx 1.618$.

Holds when each non-base call does a constant amount of work $c$ and makes exactly one recursive call on $n-1$, and the base case at $n=0$ costs $c_0$. Substitute $T(n-1)=T(n-2)+c$ repeatedly: $T(n)=T(n-k)+kc$, then put $k=n$.

Unrolling gives $M(n)=2^{k}M(n-k)+(2^k-1)$; put $k=n$. The same shape counts calls when the base case is n == 0 and is itself counted: $C(n)=2C(n-1)+1,C(0)=1\Rightarrow C(n)=2^{n+1}-1$.