c - 递归相关问题

Question

请在下面找到显示一些基于递归的操作的代码。我希望有人能解释一下这个递归是如何工作的？

#include <stdio.h>
int func(int);
main()
{
  int ret = 0;
  ret = func(6);
   printf("The val is %d\n",ret);

}

int func(int m)
{
    if((m==0)||(m==1))
    {
       return 1;
    }
    else
    {
      return (func(m-1)+func(m-2));
    }
} 

执行时，val的值为13。请有人解释一下这个展开操作是如何在堆栈中发生的

Answer 1

您不需要涉及堆栈或任何展开（不过，请原谅我涉及自己）。

只需将调用替换为函数的内容，并继续这样做，直到您不再递归：

ret = func(6) =
      func(5) + func(4) =
      func(4) + func(3) + func(3) + func(2) =
      func(2) + func(3) + func(1) + func(2) + func(1) + func(2) + func(0) + func(1) =
      func(0) + func(1) + func(1) + func(2) + 1 + func(0) + func(1) + 1 + func(1) + func(0) + 1 + 1 =
      1 + 1 + 1 + func(0) + func(1) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 =
      3 + 1 + 1 + 8 = 
      3 + 2 + 8 =
      13

排版有点困难，但这就是发生的事情，答案似乎也与你得到的相符。

Answer 2

递归只不过是从特定函数中调用 a 函数。许多数学算法或（树）搜索算法使用这种技术来获得他们想要的结果。

递归函数调用需要“逃避”它们重复的“自调用”，否则应用程序将变得无响应。在您的示例中，这是通过if((m==0)||(m==1))检查完成的。如果检查为真，则函数只返回 1（并转义递归）。

您展示的递归代码计算斐波那契数列，这是一种典型的递归算法，因为它需要 2 个先前计算的值。第 0 步和第 1 步返回1。这 2 个值是为第 2 步添加的（结果为1+1=2）。下一步导致1+2=3. 等等。如您所见，这只能从一开始就计算出来（因此需要递归才能这样做）

Answer 3

您的程序尝试打印斐波那契数列的第 n 个（或第 n+1 个）数。这里的基本情况是m =1 or m=0

这里递归的最糟糕的事情是一个值被计算了两次，例如 func(4)、func(3) 和 func(2)，从这里可以看出。