MediumFoundational

Nth Fibonacci Number

Time limit: 2 s
Memory limit: 128 MB
Estimated: 15 min

DP Foundations

Description

Write a recursive function that returns the n-th Fibonacci number, using the standard definition:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2) for n > 1

Example: n = 10 returns 55.

A naive recursive solution that re-computes the same sub-calls over and over is exponential and will be far too slow for the larger inputs in this problem. You must use memoized recursion (top-down dynamic programming: cache each fibonacci(k) the first time it is computed and reuse it) so each value is computed only once.

Constraints

0 <= n <= 50

Sample cases

Sample 1
Input
```
n = 0
```
Expected output
```
0
```
Sample 2
Input
```
n = 1
```
Expected output
```
1
```
Sample 3

Skills and languages

Concepts

Memoization

Languages

Python 3

Solve this problem

Create a free account to write, run and submit your solution.

Write Python or Java in the browser, with your draft saved as you type
Run your code on the examples as often as you like
Submit to a sandboxed judge and see exactly which case failed
Ask the AI mentor for a hint without being handed the answer

Create free account

Sample 1

Input

Expected output

Sample 2

Input

Expected output

Sample 3

Concepts

Languages

Solve this problem

Input

Expected output