Python Program to Generate Fibonacci Sequence Using Recursion

Introduction

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence typically starts as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... In mathematical terms, the Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n >= 2

Recursion is an elegant way to generate the Fibonacci sequence, as the sequence definition is naturally recursive. This tutorial will guide you through creating a Python program that generates the Fibonacci sequence using recursion.

Example:

• Function Name: fibonacci
• Function Purpose: Generate the nth Fibonacci number using recursion.
• Program Output:

  Fibonacci sequence up to 5 terms: 0, 1, 1, 2, 3
  

Problem Statement

Create a Python program that:

• Defines a recursive function named fibonacci.
• The function takes a single argument, n, which represents the position in the Fibonacci sequence.
• The function returns the nth Fibonacci number using recursion.
• The program calls the function multiple times to generate the Fibonacci sequence up to a specified number of terms.

Solution Steps

1. Define the Recursive Function: Use the def keyword to define a function named fibonacci.
2. Add Base Cases: Include base cases to return 0 for F(0) and 1 for F(1).
3. Implement the Recursive Case: In the recursive case, call the fibonacci function for n-1 and n-2, then sum the results.
4. Generate the Sequence: Use a loop to call the fibonacci function for the first n terms.
5. Display the Sequence: Print the generated Fibonacci sequence.

Python Program

# Python Program to Generate Fibonacci Sequence Using Recursion
# Author: https://www.rameshfadatare.com/

# Step 1: Define the recursive function
def fibonacci(n):
    # Step 2: Add base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Step 3: Implement the recursive case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Step 4: Generate the sequence
n_terms = 5  # Number of terms to generate

print(f"Fibonacci sequence up to {n_terms} terms:")
for i in range(n_terms):
    print(fibonacci(i), end=" ")

print()  # Newline for clean output

Explanation

Step 1: Define the Recursive Function

• The function fibonacci is defined using the def keyword. It takes one parameter, n, which represents the position in the Fibonacci sequence.

Step 2: Add Base Cases

• The base cases check if n is 0 or 1. If so, the function returns 0 or 1 respectively because F(0) = 0 and F(1) = 1.

Step 3: Implement the Recursive Case

• If n is greater than 1, the function calls itself with n-1 and n-2, and returns the sum of these two calls. This mimics the recursive definition of the Fibonacci sequence.

Step 4: Generate the Sequence

• The n_terms variable specifies how many terms of the Fibonacci sequence to generate.
• A for loop is used to call the fibonacci function for each of the first n_terms Fibonacci numbers.

Step 5: Display the Sequence

• The print() function displays the generated Fibonacci sequence, with each term printed on the same line, separated by spaces.

Output Example

Example Output:

Fibonacci sequence up to 5 terms:
0 1 1 2 3 

Additional Examples

Example 1: Fibonacci Sequence Up to 10 Terms

# Generate Fibonacci sequence up to 10 terms
n_terms = 10

print(f"Fibonacci sequence up to {n_terms} terms:")
for i in range(n_terms):
    print(fibonacci(i), end=" ")

print()  # Newline for clean output

Output:

Fibonacci sequence up to 10 terms:
0 1 1 2 3 5 8 13 21 34 

Example 2: Fibonacci Sequence Up to 15 Terms

# Generate Fibonacci sequence up to 15 terms
n_terms = 15

print(f"Fibonacci sequence up to {n_terms} terms:")
for i in range(n_terms):
    print(fibonacci(i), end=" ")

print()  # Newline for clean output

Output:

Fibonacci sequence up to 15 terms:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 

Example 3: Generate Fibonacci Number at a Specific Position

# Generate the 7th Fibonacci number
position = 7
result = fibonacci(position)
print(f"The {position}th Fibonacci number is {result}")

Output:

The 7th Fibonacci number is 13

Conclusion

This Python program demonstrates how to generate the Fibonacci sequence using recursion. The recursive approach is a natural fit for this problem, as the Fibonacci sequence is defined recursively. However, it is important to note that the recursive method can be inefficient for large values of n due to repeated calculations. Understanding recursion and how to implement it is essential for solving a wide range of problems in Python and other programming languages.