Fibonacci sequence (recursion)
Easy TimeO(2ⁿ) SpaceO(n)
The Fibonacci sequence starts 0, 1, and every term after that is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13. Given a position n, return the term sitting there. Counting starts at 0, so term 0 is 0 and term 1 is 1, and n is never negative.
Examples
Example 1
- Input
- n = 5
- Output
- 0, 1, 1, 2, 3,
55— position 5 holds 5, which is a coincidence worth not reading into.
Example 2
- Input
- n = 7
- Output
- 0, 1, 1, 2, 3, 5, 8,
1313— eight terms, and position 7 is the last of them.
The Code
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
fib(5);Done
More like this
All recursion examples (13) →- Factorial The simplest linear recursion — one call, one multiply.
- Tower of Hanoi Move a stack of disks by trusting the recursion for the rest.
- GCD (Euclid) Euclid’s algorithm — recursion that shrinks fast.
- Power Raise a number to a power one multiply at a time.
- Sum of digits Peel one digit off at a time with the modulo trick.
- Mutual recursion Two functions that call each other all the way down.