Fibonacci Number | Recursive Python Solution

Find the n-th Fibonacci number with a recursive function in Python. Clear problem statement, examples, easy-to-grasp intuition, commented code, dry run, and Big-O complexity.

The [Problem Link] is given here for your quick reference.

What does the problem ask?

For a non-negative integer n, return the n-th value in the Fibonacci sequence:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   for n ≥ 2

Examples

Also read about Leetcode #7 : Reverse Integer Python Program.

Intuition & Approach

The definition of the Fibonacci sequence is self-referencing:

• Base cases: F(0) = 0, F(1) = 1.
• Any larger F(n) equals the sum of the two previous numbers.

This naturally maps to recursion:

• If n is 0 or 1, return it right away.
• Otherwise, call the same function for n-1 and n-2, add the results, and return the sum.

Code

class Solution:
    # helper that returns F(num)
    def func(self, num):
        if num <= 1:            # base cases: F(0)=0, F(1)=1
            return num
        # recursive calls for previous two numbers
        return self.func(num - 1) + self.func(num - 2)

    def fib(self, n: int) -> int:
        # simply delegate to the helper
        return self.func(n)

Code explanation

1. func(num)
   • If num is 0 or 1, return it (ends recursion).
   • Otherwise return func(num-1) + func(num-2).
2. fib(n)
   • Acts as a thin wrapper that calls func.

The recursion tree keeps expanding until every branch hits a base case, then sums bubble back up to the original call.

Dry run for n = 5

graph TD
    A["fib(5)<br/>calls func(5)"] --> B["func(5)<br/>5 > 1, so recurse"]
    
    B --> C["func(4)<br/>4 > 1, so recurse"]
    B --> D["func(3)<br/>3 > 1, so recurse"]
    
    C --> E["func(3)<br/>3 > 1, so recurse"]
    C --> F["func(2)<br/>2 > 1, so recurse"]
    
    D --> G["func(2)<br/>2 > 1, so recurse"]
    D --> H["func(1)<br/>1 ≤ 1, return 1"]
    
    E --> I["func(2)<br/>2 > 1, so recurse"]
    E --> J["func(1)<br/>1 ≤ 1, return 1"]
    
    F --> K["func(1)<br/>1 ≤ 1, return 1"]
    F --> L["func(0)<br/>0 ≤ 1, return 0"]
    
    G --> M["func(1)<br/>1 ≤ 1, return 1"]
    G --> N["func(0)<br/>0 ≤ 1, return 0"]
    
    I --> O["func(1)<br/>1 ≤ 1, return 1"]
    I --> P["func(0)<br/>0 ≤ 1, return 0"]
    
    %% Return value annotations
    H -.-> |"returns 1"| D
    J -.-> |"returns 1"| E
    K -.-> |"returns 1"| F
    L -.-> |"returns 0"| F
    M -.-> |"returns 1"| G
    N -.-> |"returns 0"| G
    O -.-> |"returns 1"| I
    P -.-> |"returns 0"| I
    
    %% Intermediate calculations
    I -.-> |"1 + 0 = 1"| E
    E -.-> |"1 + 1 = 2"| C
    F -.-> |"1 + 0 = 1"| C
    C -.-> |"2 + 1 = 3"| B
    
    G -.-> |"1 + 0 = 1"| D
    D -.-> |"1 + 1 = 2"| B
    
    B -.-> |"3 + 2 = 5"| A
    
    %% Styling
    classDef baseCase fill:#e1f5fe,stroke:#01579b,stroke-width:2px
    classDef recursive fill:#fff3e0,stroke:#e65100,stroke-width:2px
    classDef result fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    
    class H,J,K,L,M,N,O,P baseCase
    class B,C,D,E,F,G,I recursive
    class A result

So fib(5) returns 5.

Complexity

In plain words: the recursive method is easy to write but repeats work many times, making it slow for large n. The memory used grows linearly with n because each pending call waits on its two children.

Conclusion

A direct recursive implementation follows the mathematical definition of Fibonacci numbers and is great for learning recursion. For bigger inputs you would switch to memoization or an iterative approach, but this simple version clearly shows the concept in just a few lines of Python.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.