Recursion Tree Explorer

Pick a recursive definition, set n, and see how many calls it makes and how many of them solve a problem something else already solved.

Worked example — Recursion Tree Explorer

Calls made	25
Distinct subproblems	7
Calls per subproblem	3.6
Deepest nesting	5
Base cases reached	13
Combining steps	12

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Fibonacci, computed by counting ones 🖖

Set n to 20. The tree holds 21,891 calls: 10,946 of them reach a base case, and the other 10,945 are additions. Only fib(1) returns 1, fib(0) returns 0, so 6,765 of those leaves carry a one and 4,181 carry nothing. F(20) is 6,765, which is exactly the number of ones. Every value the recursion returns is a sum of some of them, and nothing about that changes with n: the base-case card always reads F(n+1), and the ones among them always number F(n).

Two trees of 21,891 calls, and only one repeats itself 🖖

Naive fib(20) and merge sort on 10,946 items make exactly the same number of calls: 21,891, split into 10,946 base cases and 10,945 combining steps. Three of the six cards read identically, and both definitions branch two ways at every internal node, so branching is not what separates them. The distinct-subproblem card is: 21 against 21,891. A memo table collapses Fibonacci's tree to 21 units of work and leaves merge sort's at 21,891, because merge sort's halves are different slices of one array, and a cached answer for "a run of 5,473 items" would be the wrong 5,473 items.

One subtracted 1 separates φⁿ from 2ⁿ 🖖

Hanoi and Fibonacci both recurse twice and reach much the same depth, 20 against 19. Hanoi at n = 20 makes 2,097,151 calls; Fibonacci makes 21,891, which is 95.8 times fewer. The only difference in the code is the second recursive argument: Hanoi calls itself on n−1 twice, Fibonacci on n−1 and then n−2. That single subtraction drops the base of the exponential from 2 to φ = 1.618, and the gap keeps opening. At n = 30 it is 2,147,483,647 against 2,692,537, a factor of 798.

Problems solved in full

The call count closed form when naive fib(10) makes 177 calls 6 steps
The tool says naive fib(10) makes 177 calls and fib(11) makes 287. Find the closed form for the call count, prove it, and then work out how far naive Fibonacci gets in one second on a machine that manages 10⁸ calls per second.
1. Add one to each count: 178 and 288. Both are even, and their halves are 89 and 144, which are F₁₁ and F₁₂. So the conjecture is C(n) = 2F(n+1) − 1, with F(1) = F(2) = 1.
  
  $C (10) = 177, C (11) = 287 ⟹ \frac{178}{2} = 89 = F_{11}, \frac{288}{2} = 144 = F_{12}$
2. The tree explains where the doubling comes from. Every internal node makes exactly two calls and every leaf makes none, so a tree with L leaves has L − 1 internal nodes and 2L − 1 nodes altogether. The tool reports 89 base cases at n = 10, and 2 × 89 − 1 = 177.
  
  $N = 2 L - 1 ⟹ 2 \times 89 - 1 = 177$
3. Base cases first. fib(0) and fib(1) return without recursing, so C(0) = C(1) = 1, and both 2F(1) − 1 and 2F(2) − 1 equal 1.
  
  $C (0) = C (1) = 1, 2 F_{1} - 1 = 2 F_{2} - 1 = 1$
4. Now the induction step. Assume the formula at n − 1 and at n − 2. The call at n is one node plus its two subtrees, and the two Fibonacci numbers underneath collapse by the definition of the sequence itself. Setting n = 11 gives 2 × 144 − 1 = 287, which is what the tool prints.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) = 1 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 F_{n + 1} - 1$
5. Leave the tree here. Binet's formula gives F(m) = (φ^m − ψ^m)/√5 with φ = 1.6180 and |ψ| < 1, so F(m) is φ^m/√5 rounded to the nearest integer, and C(n) ≈ 2φⁿ⁺¹/√5. One second at 10⁸ calls per second buys 10⁸ calls, which fixes φⁿ⁺¹ at 1.1180 × 10⁸.
  
  $C (n) \approx \frac{2 φ ^{n + 1}}{5} = 1 0^{8} ⟹ φ^{n + 1} = \frac{1 0 ^{8} 5}{2} = 1.1180 \times 1 0^{8}$
6. Take logarithms. ln(1.1180 × 10⁸) = 18.5323 and ln φ = 0.4812, so n + 1 = 38.51 and n = 37.5. Round down, because a fractional call does not finish.
  
  $n + 1 = \frac{ln ( 1.1180 \times 1 0 ^{8} )}{ln φ} = \frac{18.5323}{0.4812} = 38.51$
Answer

n = 37. The tool confirms the two neighbours: 78,176,337 calls at n = 37, and 126,491,971 at n = 38. Past there, every further 1.44 in n doubles the work, because ln 2 / ln φ = 1.44. Meanwhile the distinct-subproblem card at n = 37 reads 38. Seventy-eight million calls to answer thirty-eight questions is the argument for dynamic programming in a single line.
Three branches that grow slower than two 6 steps
Three-step stairs calls itself three times at every node; Towers of Hanoi calls itself twice. Load Stairs at 20, three branches, work out which of the two trees grows faster, and decide what the branching factor is worth as a guide.
1. Read the recurrence off the definition rather than off the picture. One call for the node itself, then three more at n − 1, n − 2 and n − 3, and anything at 2 or below returns without recursing.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) + C (n - 3), C (0) = C (1) = C (2) = 1$
2. Assume the count grows geometrically, C(n) ≈ A xⁿ, and substitute. Divide through by x raised to n − 3 and the leading 1 is left behind as lower-order noise, which leaves a cubic. Its only real root is 1.8392868, the tribonacci constant.
  
  $C (n) \sim A x^{n} ⟹ x^{3} = x^{2} + x + 1 ⟹ x = 1.8392868$
3. The same recipe on the other two definitions. Fibonacci calls itself at n − 1 and n − 2, so x² = x + 1 and the root is φ = 1.6180340. Hanoi calls itself twice at n − 1, so x = 2 and there is nothing to solve.
  
  $fib : x^{2} = x + 1 \Rightarrow φ = 1.6180340; hanoi : C (n) = 1 + 2 C (n - 1) \Rightarrow x = 2$
4. Check it rather than believe it. Set n to 29, read the calls card, set n to 30, read it again, divide. Stairs gives 1.83929, Fibonacci 1.61803, Hanoi exactly 2. Five decimal places on all three.
  
  $\frac{C ( 30 )}{C ( 29 )} : \frac{56 , 843 , 233}{30 , 905 , 041} = 1.83929, \frac{2 , 692 , 537}{1 , 664 , 079} = 1.61803, \frac{2 ^{31} - 1}{2 ^{30} - 1} = 2.00000$
5. What the root does not give you is the count. 1.8393²⁰ is 196,331 while the card reads 128,287, so there is a factor of 0.65 sitting in front; Hanoi's calls are exactly 2ⁿ⁺¹ − 1, a factor of 2. The base cases set that constant and the recurrence sets the root, and only the root decides who wins eventually.
  
  $1.839 3^{20} = 196, 331 against 128, 287 ⟹ A = 0.6534; hanoi : C (n) = 2^{n + 1} - 1, A = 2$
6. Eventually arrives quickly here. At n = 20 Hanoi makes 16.3 times as many calls as stairs, and at n = 30 it makes 37.8 times as many. The ratio doubles every 8.3 steps, since ln 2 divided by ln(2 ÷ 1.8393) is 8.27.
  
  $\frac{2 ^{21} - 1}{128 , 287} = 16.3, \frac{2 ^{31} - 1}{56 , 843 , 233} = 37.8, \frac{ln 2}{ln ( 2/1.8393 )} = 8.27$
Answer

Hanoi grows faster, 2 against 1.8393, and the third branch costs stairs nothing it cannot afford. The branching factor is an upper bound on the growth rate, and it is reached only when every child is one step smaller. Stairs spends two of its three calls on arguments that are 2 and 3 smaller, and those subtrees are cheap enough that they never add up to the branch it appeared to gain.

The recipe is the part to keep, because it works on a definition nobody has already solved for you. Count the children, note how far each one drops the argument, write x to the largest drop as the sum of x to the remaining drops, and take the largest real root. One caution goes with it: this is a fact about the naive tree, and the naive tree is not what anyone would write. The distinct-subproblem card reads 21 at n = 20 for stairs and 21 for Hanoi, so a memo removes the exponent altogether and the growth rate stops mattering.

$x^{k} = j \sum m_{j} x^{k - j} (m_{j} children at n - j, k = max j) : 1.8393 < 2$

Learning path

Counting work, not seconds

Leads to Pathfinding

By the 42Math team · Updated 2026-08-26

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

Fibonacci at 20 - 21,891 calls over 21 distinct subproblems: 1,042.4 calls each
Merge sort, same call count - The same 21,891 calls, and every one of them a different subproblem
Hanoi at 20 - 2,097,151 calls over 21 distinct subproblems, and 1,048,575 disc moves
Pascal's rule, C(20,10) - 369,511 calls to fill in 120 cells of Pascal's triangle
Stairs at 20, three branches - Three branches instead of two: 128,287 calls, 21 subproblems