Intermediate · 25 minYou are hereRead
Recursion
A recursive function calls itself on a smaller problem, each call in its own frame, until a base case answers. The frames pile up, then fold back as the answers return.
Recursion
Recursion
Lessons on this topic
Intermediate · 20 minYou are hereRead
Head and tail recursion
Work done before the recursive call happens on the way down; work done after it happens on the way back, in reverse order. A call made last can become a loop.
Intermediate · 25 minYou are hereRead
Tree recursion
A function that calls itself twice makes a tree of calls. The tree grows exponentially with n, while the stack holds only one path through it.
Advanced · 25 minYou are hereRead
Indirect and nested recursion
Recursion can pass through another function and come back, and a recursive call can sit inside the argument of another, as in Ackermann’s function.
Intermediate · 25 minYou are hereRead
Fast powers
Since x to the n is the square of x to the n/2, a power needs about log₂ n squarings instead of n − 1 multiplications, and the bits of n say where to multiply by x.
Intermediate · 25 minYou are hereRead
Taylor series and Horner's rule
A few terms of a Taylor series make a polynomial, and Horner’s nesting evaluates it with one multiplication and one addition per term, by recursion or by a loop.
Intermediate · 25 minYou are hereRead
Memoisation
Storing each answer the first time it is computed turns fib’s tree of calls into a single line of calls; filling the table from the bottom up removes the recursion as well.
Intermediate · 25 minYou are hereRead
Binomial coefficients
C(n, r) = C(n − 1, r − 1) + C(n − 1, r) fills Pascal’s triangle row by row. The plain recursion repeats work as fib does; one row of storage removes it.
Intermediate · 25 minYou are hereRead
The Tower of Hanoi
To move n discs, move n − 1 out of the way, move the largest, and move the n − 1 back on top: 2ⁿ − 1 moves, and no plan does better.
Related topics