递归添加数字时避免堆栈溢出

本文关键字：堆栈 栈溢出 添加 数字 递归 | 更新日期: 2023-09-27 18:24:01

我有一个递归函数，它在第一个递归调用上添加值number，在第二个递归调用中添加number-1，依此类推，直到它达到0。我已将此功能实现为：

public static int func(int number, int retval=0)
{
    if (number<=0)
        return retval;
    return func( number-1, retval+number );
}

当使用大的number值调用它时，如何在不创建堆栈溢出的情况下编写它？我需要一个单独的文件吗？

递归添加数字时避免堆栈溢出

在第一个递归调用中添加number，在第二个递归调用添加number-1，依此类推，直到最后添加0并停止递归。因此，这相当于只返回retval + number + (number-1) + ... + 1，它等于retval + (number+1)*number/2。

因此，您可以通过将函数替换为：来避免完全递归（以及堆栈溢出的可能性）

public static int func(int number, int retval=0)
{
    if (number<=0) {
        return retval;
    } else {
        return retval + (number+1)*number/2;
    }
}

这种方法的另一个好处是，它在O(1)运行时运行，而问题中的递归方法及其迭代方法都在O(number)运行时运行。

当您有一个类似于您的递归函数，它不对递归调用的结果进行操作，而是将其返回给调用者时，您可以用适当的参数替换跳到函数体顶部来替换递归调用。

对于您的功能：

public static int func(int number, int retval=0)
{
    if (number<=0)
        return retval;
    return func( number-1, retval+number );
}

看起来是这样的：

public static int func(int number, int retval=0)
{
top:
    if (number<=0)
        return retval;
    //return func( number-1, retval+number );
    number = number - 1;
    retval = retval + number;
    goto top;
}

为了摆脱难看的goto，可以用while循环来代替（因为退出条件在顶部）。

现在函数看起来是这样的：

public static int func(int number, int retval=0)
{
  while (! number<=0)
  {
    number = number - 1;
    retval = retval + number;
  }
  return retval;
}

它不再是递归的，也不会导致堆栈溢出。

如果必须使用递归，请在函数中添加一个整数，该整数包含堆栈中剩余的"空间"，例如：

public static int func(int number, int retval=0, int numberOfCalls)
{
    if(numberOfCalls >= maximumBeforeStackOverflow)
    {
        //throw exception you can catch (you can't cath stackoverflow if i'm correct)
        //or break func
    }
    if (number<=0)
    {
        return retval;
    }
    return func( number-1, retval+number, numberOfCalls++ );
}
相关文章：