Nth Fibonacci Recursively
Find a Fibonacci value by its zero-based index using Python recursion. Students trace two base cases, branching calls, and repeated work in the call tree.
1def fibonacci(n):2 # Base cases3 if n == 0:4 return 05 if n == 1:6 return 178 # Recursive case9 return fibonacci(n - 1) + fibonacci(n - 2)1011# Test12n = int(input("Enter n: "))13result = fibonacci(n)14print(f"Fibonacci({n}) = {result}")
Output
Enter n: 7 Fibonacci(7) = 13
In this one
- Index Fibonacci values
- Use two base cases
- Recognize repeated recursion
How it works
- 1
Return zero or one at the matching base index.
- 2
Request indexes n - 1 and n - 2.
- 3
Add those results and return their sum.
Edge cases
Does index one return zero?
Does index one return zero?
No. It returns one.
Is this efficient for a large index?
Is this efficient for a large index?
No. Many Fibonacci values are recomputed repeatedly.
What's going on
Index zero returns zero and index one returns one. Every larger index requests the two previous values and adds them.
For index four, the result is three. This branching recursion repeats many subproblems, so runtime grows quickly even before very deep calls become a concern. Python's call stack records unfinished requests; negative indexes do not reach either base case.
Does index one return zero? No. It returns one.
Is this efficient for a large index? No. Many Fibonacci values are recomputed repeatedly.
Quiz
Tap an option. The answer stays hidden until you pick.
Question 1
What is fibonacci(4)?
Pick an answer to check it.
Question 2
Does index one return zero?
Pick an answer to check it.
Questions people ask
Does index one return zero?
No. It returns one.
Is this efficient for a large index?
No. Many Fibonacci values are recomputed repeatedly.
What is fibonacci(4)?
3.
๐Related Content
- ๐
Phase 3 - Learn Concepts
Review Phase 3 concepts and explanations
- ๐
Phase 3 - Quiz
Test your Phase 3 understanding with quiz questions
- ๐ป
Phase 3 - All Practice Problems
Explore all practice problems for Phase 3
- ๐
Master Your Logic Building - Complete Course
Browse all phases and tutorials
- ๐ง
Logic Building Overview
Learn about the complete logic building curriculum