Nth Fibonacci Number, Recursively

Easy ⏱ 8 min 88% acceptance ★★★★☆ 4.2
Implement fib(n) that returns the nth Fibonacci number using plain recursion (no memoization, no loops). fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n >= 2.

Examples

Example 1
Input
fib(0)
Output
0
Explanation

Base case.

Example 2
Input
fib(6)
Output
8
Explanation

Sequence: 0,1,1,2,3,5,8 — index 6 is 8.

Constraints

  • 0 <= n <= 25 (kept small since plain recursion is exponential).

Topics

RecursionMath

Companies

GoogleWiproCognizant

Hints

Hint 1

Two base cases: n == 0 and n == 1.

Hint 2

Recursive case: fib(n - 1) + fib(n - 2).

← Factorial the Recursive Way Sum of Digits via Recursion →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.