Python Program to Find Fibonacci Using Recursion

You can find the Fibonacci number using recursion in Python by defining a function like def fibonacci(n): return n if n <= 1 else fibonacci(n-1) + fibonacci(n-2) which calls itself to calculate previous Fibonacci numbers.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, think of the sequence as starting with 0 and 1, and each next number is the sum of the two before it. Using recursion means the function calls itself with smaller numbers until it reaches the base cases where n is 0 or 1.

Algorithm

1

Check if the input number is 0 or 1; if yes, return the number itself.

2

Otherwise, call the function recursively for the two previous numbers: <code>n-1</code> and <code>n-2</code>.

3

Add the results of these two recursive calls.

4

Return the sum as the Fibonacci number for <code>n</code>.

Code

python

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

Output

55

Dry Run

Let's trace fibonacci(4) through the code

1

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

2

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

3

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

4

Call fibonacci(1)

Base case: return 1

5

Call fibonacci(0)

Base case: return 0

6

Return fibonacci(2)

1 + 0 = 1

7

Return fibonacci(1)

Base case: return 1

8

Return fibonacci(3)

1 + 1 = 2

9

Call fibonacci(2)

Call fibonacci(1) + fibonacci(0) = 1 + 0 = 1

10

Return fibonacci(4)

2 + 1 = 3

Function Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(1)	1
fibonacci(3)	2
fibonacci(2)	1
fibonacci(4)	3

Why This Works

Step 1: Base Case

The function returns n directly if it is 0 or 1, stopping the recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to find the two previous Fibonacci numbers.

Step 3: Combining Results

It adds the results of these two calls to get the Fibonacci number for n.

Alternative Approaches

Iterative approach

python

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_iterative(10))

This method uses a loop and is faster and uses less memory than recursion.

Memoization (caching results)

python

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

print(fibonacci_memo(10))

This method stores results to avoid repeated calculations, making recursion efficient.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive function calls itself twice for each non-base case, leading to exponential growth in calls.

Space Complexity

The maximum depth of the recursion stack is n, so space used is proportional to n.

Which Approach is Fastest?

Iterative and memoized methods run in linear time O(n), much faster than simple recursion.

Approach	Time	Space	Best For
Simple Recursion	O(2^n)	O(n)	Learning recursion basics
Iterative	O(n)	O(1)	Efficient calculation
Memoization	O(n)	O(n)	Efficient recursion with caching