Next
1. Print 1 to N Recursively2. Factorial Using Recursion3. Print N to 1 Recursively4. Even Numbers 1-N Recursively5. Odd Numbers 1-N Recursively6. Sum of First N Natural Numbers Recursively7. Power x^n Recursively8. Nth Fibonacci Recursively9. Fibonacci Series Recursively10. Sum of Digits Recursively

Nth Fibonacci Recursively

Find nth Fibonacci number recursively.

IntermediatePhase 3 - Level 1: Basic RecursionExample 8 of 10
nth-fibonacci-recursively.py
1def fibonacci(n):
2    # Base cases
3    if n == 0:
4        return 0
5    if n == 1:
6        return 1
7    
8    # Recursive case
9    return fibonacci(n - 1) + fibonacci(n - 2)
10

11# Test
12n = int(input("Enter n: "))
13result = fibonacci(n)
14print(f"Fibonacci({n}) = {result}")

Output

Enter n: 7
Fibonacci(7) = 13

What's going on

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2).

Key Concepts:

Base cases: F(0) = 0, F(1) = 1
Recursive: sum of previous two
Each term depends on two previous

🔗Related Content

PreviousPower x^n RecursivelyNextFibonacci Series Recursively