easyNumber ProblemsJava

Find the Nth Fibonacci Number Using Recursion

Return the Nth Fibonacci number using a recursive definition.

Quick Answer

Define fib(n) as fib(n - 1) + fib(n - 2), with base cases fib(0) = 0 and fib(1) = 1. Each call branches into two smaller calls until it reaches a base case. It is elegant but exponential; memoization or iteration makes it fast.

Problem Statement

In the Fibonacci sequence, fib(0) = 0, fib(1) = 1, and every later term is the sum of the two preceding terms: fib(n) = fib(n - 1) + fib(n - 2). So the sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... (0-indexed).

Given an index n (0-based), return the Nth Fibonacci number using recursion. You may assume n is small enough that plain recursion finishes in reasonable time.

Input: A single non-negative integer n (0-based index).

Output: The Nth Fibonacci number.

Examples

Example 1
Input:  9
Output: 34

The sequence 0,1,1,2,3,5,8,13,21,34 has 34 at index 9.

Example 2
Input:  6
Output: 8

At index 6 the sequence value is 8 (0,1,1,2,3,5,8).

Constraints

  • 0 <= n <= 40 keeps naive recursion fast enough
  • Solve it recursively with two base cases

Think Before You Code

Reveal the questions to ask yourself first
  • What are the two base cases that stop the recursion?
  • Which two smaller subproblems does fib(n) depend on?
  • Why does naive recursion recompute the same values many times?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
You need two base cases here, not one: fib(0) = 0 and fib(1) = 1.
Hint 2
The recursive step is `return fib(n - 1) + fib(n - 2)`.
Hint 3
Note that fib(n - 2) gets recomputed inside fib(n - 1); that repetition is why the naive version is slow.

Approach

Reveal the step-by-step approach

Translate the mathematical definition directly into recursion.

  1. Base cases: if n < 2, return n (covers fib(0) = 0 and fib(1) = 1).
  2. Recursive case: return fib(n - 1) + fib(n - 2).

Every call spawns two more calls, forming a binary tree of calls. It is simple to write but recomputes subproblems, so it is exponential in time.

Dry Run

Walk through the example step by step

Computing fib(6) as a call tree (truncated):

fib(6)
 = fib(5) + fib(4)
 fib(5) = fib(4) + fib(3)
 fib(4) = fib(3) + fib(2)
 fib(3) = fib(2) + fib(1)
 fib(2) = fib(1) + fib(0) = 1 + 0 = 1
 ...
 values: fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8

Final result: 8

Solution

Reveal the full Java solution
public class FibonacciRecursion {
    public static int fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(9)); // 34
        System.out.println(fibonacci(6)); // 8
    }
}

Returning n directly when n < 2 neatly encodes both base cases at once, since fib(0) = 0 and fib(1) = 1. The recursion mirrors the math exactly but repeats work: fib(n - 2) is recomputed inside fib(n - 1), which is why the running time grows exponentially and memoization is the usual fix.

Time: O(2^n) for naive recursionSpace: O(n) for the recursion call stack

Common Mistakes

  • Providing only one base case, so fib(1) recurses into fib(0) and fib(-1).
  • Assuming it is fast for large n; without memoization it becomes unusably slow.

Edge Cases to Test

  • fib(0) returns 0 and fib(1) returns 1 straight from the base cases.
  • Large n (for example 45+) is extremely slow with naive recursion.

Interview Follow-Ups

  • How would memoization or a bottom-up table reduce this to O(n)?
  • How would you compute the Nth Fibonacci number iteratively in O(1) space?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us