JavaScript Program for Fibonacci Using Recursion

You can find the Fibonacci number using recursion in JavaScript with function fibonacci(n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return it directly. Otherwise, calculate it by adding the Fibonacci numbers at positions n-1 and n-2 using recursion.

Algorithm

1

Get input number n.

2

If n is 0 or 1, return n.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number for n.

Code

javascript

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10));

Output

55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, call fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

5

Base cases

fibonacci(1) returns 1, fibonacci(0) returns 0

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Function Call	Returned Value
fibonacci(0)	0
fibonacci(1)	1
fibonacci(2)	1
fibonacci(3)	2
fibonacci(4)	3
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly if it is 0 or 1, stopping the recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice to get the two previous Fibonacci numbers.

Step 3: Combining Results

It adds the two results to get the Fibonacci number for n.

Alternative Approaches

Iterative approach

javascript

function fibonacciIterative(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return n === 0 ? 0 : b;
}
console.log(fibonacciIterative(10));

This method uses a loop and is faster and uses less memory than recursion.

Memoization (caching results)

javascript

const memo = {};
function fibonacciMemo(n) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
  return memo[n];
}
console.log(fibonacciMemo(10));

This method stores results to avoid repeated calculations, improving performance.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive Fibonacci function calls itself twice for each non-base case, leading to exponential time O(2^n).

Space Complexity

The space used is O(n) due to the call stack depth from recursion.

Which Approach is Fastest?

Iterative and memoized methods run in O(n) time and are much faster than plain recursion.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simple code, small n
Iterative	O(n)	O(1)	Fast and memory efficient
Memoization	O(n)	O(n)	Fast with recursion, caches results