Fibonacci Number

LeetCode

LeetCode: https://leetcode.com/problems/fibonacci-number/

The Fibonacci numbers are defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n > 1

Given n, calculate F(n).

1def fib(n: int) -> int:
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)
Next
Pow(x, n)
idx
4
0
3
1
2
2
Step 1 / 3
Step 1:
Call fib(4). It expands to fib(3) + fib(2).
Pointers: idx=0
Focus: select @ [0]