怎样理解递归函数缓存的过程？

Question

问题遇到的现象和发生背景

做python入门技能树题目时，无法理解代码是如何实现的
https://edu.csdn.net/skill/practice/python-3-9/239
我不理解cache是怎样存入字典的，并且为什么是key能从3开始。

我希望能够理解的代码

def fibonacci_inner1(n, cache):
if n == 1 or n == 2:
return 1
if cache.get(n) is not None:
return cache[n]
else:
cache[n] = fibonacci_inner1(n-1, cache) + fibonacci_inner1(n-2, cache)
return cache[n]

def fibonacci1(n):
print(fibonacci_inner1(n, {}))

运行结果及报错内容

为了能够知道这段代码如何运行，我把过程print出来了，标记为：
if cache.get(n) is not None:
print("01 Part", cache)
return cache[n]
else:
cache[n] = fibonacci_inner1(n-1, cache) + fibonacci_inner1(n-2, cache)
print("02 Part", cache)
return cache[n]

计算fibonacci1(5)运行结果则是：
02 Part {3: 2}
02 Part {3: 2, 4: 3}
01 Part {3: 2, 4: 3}
02 Part {3: 2, 4: 3, 5: 5}
5

我的解答思路和尝试过的方法

最初的{}因为get()而返回None，于是开始计算cache[n] = fibonacci_inner1(n-1, cache) + fibonacci_inner1(n-2, cache)，可是在第一次运算时，fibonacci_inner1(n-1, cache)中的cache值是什么？
而且最开始给n赋值为5，但第一个蹦出的结果却是cache[3] = 2，这个键值对是怎么来的呢？

我想要达到的结果

希望能好心解释一下逻辑过程，我知道能from functools import lru_cache，但对于上述问题无法释怀。

Answer 1

这就是递归和递推的区别
递归是从后往前算，比如你要求的是第5个斐波那契数，就必须回头去计算第4个和第3个，如果第4个也还没计算出来，就再回头去计算第3个和第2个。
你的代码里，最初的{}因为get()而返回None，于是开始计算cache[n] = fibonacci_inner1(n-1, cache) + fibonacci_inner1(n-2, cache)，这里递归计算的时候，cache依然还是空字典，因为cache[4]和cache[3]也还没有键值对，所以还要继续递归计算。一直到cache[3]=cache[2]+cache[1]的时候，因为n==1或n==2，才能得到cache[3]=2，所以也就是第一个键值对。但是cache[1]和cache[2]并没有被记入字典，而是直接返回了。如果你想看见的话，就要在这里加上：
if n == 1 or n == 2:
cache[n]=1
return 1