Fibonacci Using Recursion in Java
Problem
The Nth Fibonacci number is defined recursively as the sum of the two terms before it, so the same definition that describes the value can be used directly as the function that computes it.
Given a position n, find the Fibonacci number at that position using recursion.
Java Program
public class FibonacciAtN {
static int fib(int n) {
if (n <= 1) return n; // positions 0 and 1 are defined directly
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci number at position " + n + ": " + fib(n));
}
}Output
Core Logic
Calling the function on the two smaller positions and adding their results mirrors the mathematical definition exactly, with no loop or running total needed.
- 1The base cases
if (n <= 1) return n;handle positions 0 and 1 directly, since those are defined values, not derived ones. - 2Every other call returns
fib(n - 1) + fib(n - 2), the sum of the two preceding terms. - 3Each call branches into two further calls rather than descending in a single line, so the call tree grows wide rather than deep.
- 4Only the single result for position
nis ever printed — no intermediate terms are collected along the way.
n = 10, the calls branch all the way down to the base cases and back up, eventually combining into 55, the 10th Fibonacci number.Key Point: This only computes the one term asked for — it just happens to internally recompute several smaller terms many times over along the way, since the two branches at every level overlap heavily.
Why: Each call branches into two further calls, so the total number of calls roughly doubles with every additional position, while the deepest chain of pending calls only ever reaches n frames.