Python Program to Print Fibonacci Using Recursion

You can print Fibonacci numbers using recursion in Python by defining a function like def fibonacci(n): return n if n <= 1 else fibonacci(n-1) + fibonacci(n-2) and then calling it in a loop to print the sequence.

Examples

Input5

Output0 1 1 2 3

Input1

Output0

Input0

Output

How to Think About It

To print Fibonacci numbers using recursion, think of the sequence as each number being the sum of the two before it. The function calls itself with smaller numbers until it reaches the base cases 0 or 1, which are known values. Then it adds these results back up to get the Fibonacci number for the original input.

Algorithm

1

Define a function that takes a number n.

2

If n is 0 or 1, return n as the base case.

3

Otherwise, return the sum of the function called with n-1 and n-2.

4

Use a loop from 0 to the desired count to call the function and print each Fibonacci number.

Code

python

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

n = 5
for i in range(n):
    print(fibonacci(i), end=' ')

Output

0 1 1 2 3 

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)

Return 1 (base case)

5

Call fibonacci(0)

Return 0 (base case)

6

Return from fibonacci(2)

1 + 0 = 1

7

Call fibonacci(1)

Return 1 (base case)

8

Return from fibonacci(3)

1 + 1 = 2

9

Call fibonacci(2)

Return 1 (from previous calculation)

10

Return from fibonacci(4)

2 + 1 = 3

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

Why This Works

Step 1: Base Case

The function returns n directly when n 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 get the two previous Fibonacci numbers.

Step 3: Summing Results

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

Alternative Approaches

Iterative approach

python

def fibonacci_iter(n):
    a, b = 0, 1
    for _ in range(n):
        print(a, end=' ')
        a, b = b, a + b

fibonacci_iter(5)

This method is faster and uses less memory because it avoids recursive calls.

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]

n = 5
for i in range(n):
    print(fibonacci_memo(i), end=' ')

This method speeds up recursion by storing results to avoid repeated calculations.

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

Time Complexity

The recursive Fibonacci 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 is linear.

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
Memoization	O(n)	O(n)	Efficient recursion with caching
Iterative	O(n)	O(1)	Fastest and simplest for large inputs