Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

Nth Fibonacci Recursively

Find a Fibonacci value by its zero-based index using Python recursion. Students trace two base cases, branching calls, and repeated work in the call tree.

IntermediatePhase 3 - Level 1: Basic RecursionExample 8 of 10
nth-fibonacci-recursively.py
1def fibonacci(n):
2 # Base cases
3 if n == 0:
4 return 0
5 if n == 1:
6 return 1
7
8 # Recursive case
9 return fibonacci(n - 1) + fibonacci(n - 2)
10
11# Test
12n = int(input("Enter n: "))
13result = fibonacci(n)
14print(f"Fibonacci({n}) = {result}")

Output

Enter n: 7
Fibonacci(7) = 13

In this one

  • Index Fibonacci values
  • Use two base cases
  • Recognize repeated recursion

How it works

  1. 1

    Return zero or one at the matching base index.

  2. 2

    Request indexes n - 1 and n - 2.

  3. 3

    Add those results and return their sum.

Edge cases

Does index one return zero?

Does index one return zero?

No. It returns one.

Is this efficient for a large index?

Is this efficient for a large index?

No. Many Fibonacci values are recomputed repeatedly.

What's going on

Index zero returns zero and index one returns one. Every larger index requests the two previous values and adds them.

For index four, the result is three. This branching recursion repeats many subproblems, so runtime grows quickly even before very deep calls become a concern. Python's call stack records unfinished requests; negative indexes do not reach either base case.

Does index one return zero? No. It returns one.

Is this efficient for a large index? No. Many Fibonacci values are recomputed repeatedly.

Quiz

Tap an option. The answer stays hidden until you pick.

Question 1

What is fibonacci(4)?

Pick an answer to check it.

Question 2

Does index one return zero?

Pick an answer to check it.

Questions people ask

Does index one return zero?

No. It returns one.

Is this efficient for a large index?

No. Many Fibonacci values are recomputed repeatedly.

What is fibonacci(4)?

3.