w3resource

Python Data Structures and Algorithms - Recursion: Fibonacci sequence


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:

Flowchart: Recursion: Fibonacci sequence.

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.

Go to:


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.

Python Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.