Python Data Structures and Algorithms - Recursion: Fibonacci sequence

Last update on March 27 2025 12:50:25 (UTC/GMT +8 hours)

5. Fibonacci Sequence Using Recursion

Write a Python program to solve the Fibonacci sequence using recursion using recursion.

Sample Solution:

Python Code:

# Define a function named fibonacci that calculates the nth Fibonacci number
def fibonacci(n):
    # Check if n is 1 or 2 (base cases for Fibonacci)
    if n == 1 or n == 2:
        # If n is 1 or 2, return 1 (Fibonacci sequence starts with 1, 1)
        return 1
    else:
        # If n is greater than 2, recursively call the fibonacci function
        # to calculate the sum of the (n-1)th and (n-2)th Fibonacci numbers
        return fibonacci(n - 1) + fibonacci(n - 2)

# Print the result of calling the fibonacci function with the input value 7
print(fibonacci(7))

Sample Output:

13

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to generate the nth Fibonacci number using a naive recursive method.
• Write a Python program to generate a list of Fibonacci numbers up to n terms recursively.
• Write a Python program to implement a recursive Fibonacci function with memoization to optimize performance.
• Write a Python program to recursively compute the Fibonacci sequence and print each term as it is generated.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to get the factorial of a non-negative integer.
Next: Write a Python program to get the sum of a non-negative integer.