计算递归函数所需的内存量

本文关键字：内存 递归函数 计算 | 更新日期: 2023-09-27 18:00:58

我有以下功能：

public static long Fibon(long num)
{
    if (num == 1)
    {
        return 1;
    }
    else if (num == 2)
    {
        return 1;
    }
    return fibon(num - 1) + fibon(num - 2);
}

这个函数使用递归来计算斐波那契数。在执行此函数之前，如何计算执行此函数所需的堆栈内存量？例如，我想在几个有大数字的独立线程中执行这个函数，在执行线程之前，我想知道我需要多少可用的堆栈内存。

计算递归函数所需的内存量

只要看一下，代码就不会工作，因为当num==2时，该方法会尝试查找fibon(0(。

尝试

public static long Fibon(long num)
{
    if (num == 1)
    {
        return 1;
    }
    else if (num == 2)
    {
        return 1;
    }
    return fibon(num - 1) + fibon(num - 2);
}

会给你1，1，2，3，5。。。

很抱歉，这不是一个答案，我没有资格发表评论。

编辑：你还可以使用ulong计算更多的条目。

由于您只需记住前两项即可计算当前项，因此如果使用非递归过程，则不会遇到任何内存问题：

public static long Fibon(long num)
{
  long result ;
  if (num == 1) { return 1; }
  else if (num=2) { return 1; }
  long grandfather = 1 ;
  long father = 1 ;
  for (in i=2;i<=num;i++) 
  {
    result = father + grandFather;
    grandfather = father ;
    father = result ;
  }
  return result ;
}

对于第1个CCD_斐波那契项，函数所需的内存量是O(n)，即斐波那奇序列中该项的索引中的线性。更准确地说，它将是每次递归调用所需内存量的n-1倍，这取决于实现(加上一些常量(。

所需的内存量等于每次递归调用中的内存量加上"执行树"的"深度"。在每个递归调用中，您可以终止或进行两个新调用，一个对参数n-1，一个在参数n-2；显然这必须在CCD_ 6调用之后停止。

如果你把整个过程想象成一个带有标记为f(k)的节点的二叉树，其中节点f(k)有一个标记为f(k-1)的左子节点和一个标记了n0的右子节点，那么f的空间复杂度对应于执行树的深度。

我相信所需的long数实际上等于返回的long。

要返回2，您需要添加2个长度。要返回3，您需要将返回2所需的长度(即2个长度(与1相加，1==3。这种模式还在继续。

由于长是64位，因此所需的内存等于fibonacci值*64位。

相关文章：