The Fibonacci numbers are F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2). Read n and print F(n).
What to build
A function that follows a rule defined in terms of itself.
Requirements
- Read
n. - Print
F(n), usingF(0) = 0andF(1) = 1.
Input
One whole number n from 0 to 20.
Output
The value of F(n).
Constraints
n is from 0 to 20.
Example
Input:
6
Output:
8
Why it works
The definition translates directly into code. For larger values this version becomes slow, and the memoization lesson shows why and how to fix it.
Examples
Example 1 · Input
6
Expected output
8
Example 2 · Input
0
Expected output
0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Two base cases: fib(0) = 0 and fib(1) = 1.
Hint 2
Visualize fib(4) to see how many calls one answer needs.
Solution
Show one correct solution (try it yourself first)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
n = int(input())
print(fib(n))