ntFibonacci的大内存消耗是多少

Question

给定以下递归函数，如何计算大内存消耗？你知道吗

def nthFib(n):
    if n == 0:
       return 0

    elif n == 1:
         return 1

    return n * nthFin(n-1)

Answer 1

                 +
    def nthFib(n):
        if n == 0:
           return 0

        elif n == 1:
             return 1

        return n * nthFin(n-1)  
                 -+

以上代码部分在O（1）时间运行。 但您将为以下实例调用该代码：n，n-1，n-2。。。。1, 0 . 你知道吗

n+1次之和：意味着：O（1）*n+1=O（n+1）或O（n）

Answer 2

在内存使用的峰值，它有N个栈帧，每个栈帧都有一个等待相乘的因子。那需要O（N）内存。你知道吗

---

这个数字可以用O（1）存储器来计算。你知道吗

如果Python消除了尾部递归，那么下面将使用O（1）内存：

def _nthFib(acc, n):
    if n == 1:
         return acc

    return _nthFin(acc*n, n-1)

def nthFib(n):
    if n == 0:
       return 0

    return _nthFin(1, n)

如果Python的range是一个真正的迭代器，那么下面使用O（1）内存：

def nthFib(n):
    if n == 0:
       return 0

    acc = 1
    for x in range(2, n):
         acc *= x;

    return acc