c - 在使用递归函数调用时何时使用 'return' ？

Question

在使用递归函数调用时，我很困惑何时使用“return”。

我正在尝试找到两个数字的“GCD(最大公约数)”。我实际认为可行的是:

  include <stdio.h>
  int gcd (int a, int b);

  int main ()
  {
   int a, b;
   printf ("Enter two numbers \n");
   scanf ("%d %d", &a, &b);
   printf ("GCD for numbers %d and %d is %d\n", a, b, gcd(a,b));
   return (0);
   }

   int gcd (int a, int b)
   {
    while (a!=b)
     {
      if (a > b)
       gcd(a-b,b);
      else if (b > a)
       gcd(a,b-a);
     }
    return (a);
   }

但上面的代码不断地从终端接受数字并且无法运行代码。

但是，当我按如下方式替换函数定义时，代码会按预期工作并返回正确的值。

   int gcd (int a, int b)
   {
    while (a!=b)
     {
      if (a > b)
       return gcd(a-b,b);
      else if (b > a)
       return gcd(a,b-a);
     }
    return (a);
   }

如您所见，唯一的变化是在递归函数调用之前添加了“return”。为什么在我调用 gcd(arg1, arg2) 函数的两种情况下都需要 return？

Answer 1

Why is return required there considering in both the cases I am calling the gcd(arg1, arg2) function?

出于同样的原因，在您调用函数并希望返回该函数调用返回的值时，它也是必需的；因为调用它只会调用它，不会对结果值做任何其他事情。

I am confused when to use 'return' while using recursive function calls.

使用 return 进行递归调用，只要您将 return 用于任何其他函数调用 - 即:何时以及因为该调用返回您希望返回的值这次回来。

假设我们有

#include "magic.h" /* defines gcd2(), which computes GCD in some mysterious way */

然后我们不进行递归调用，而是将一些工作委托(delegate)给它:

/* Of course this solution also works, but is not interesting
int gcd(int a, int b)
{
    return gcd2(a, b);
} */

/* So, let's do something that actually shows off the recurrence relation */
int gcd(int a, int b)
{
    if (a > b)
        return gcd2(a-b, b);
    else if (b > a)
        return gcd2(a, b-a);
    else
        return a;
}

(我还删除了while循环，因为它与算法无关；当然，在任何情况下都会到达return，这会打破循环.)

我想我不需要复习数学理论；而且我认为很清楚为什么 gcd2 结果需要 return。

但是如何委托(delegate)工作实际上并不重要；如果 gcd 是一个可以正确计算 GCD 的函数，并且 gcd2 也是这样，那么对 gcd2 的调用可能会被对 gcd。这是 secret - 递归调用函数与正常调用函数实际上没有什么不同。只是考虑到这种可能性，需要更清楚地了解调用函数的工作原理以及它实际上做了什么。

---

当然，也可以充分利用原始的 while 循环 - 通过在执行递归之前尽可能多地减去 out。这可能看起来像:

int gcd(int a, int b)
{
    if (a > b)
        while (a > b)
            a -= b; /* prepare a value for the recursion. */
        return gcd(a, b); /* and then recurse with that value. */
    else if (b > a)
        while (b > a)
            b -= a; /* similarly. */
        return gcd(a, b);
    else /* a == b */
        return a;        
}

但是我们不妨一路走下去并转换为迭代方法:

int gcd(int a, int b)
{
    while (a != b)
        /* whichever is greater, adjust it downward, leaving an (a, b)
           pair that has the same GCD. Eventually we reach an equal pair,
           for which the result is known. */
        if (a > b)
            a -= b;
        else
            b -= a;
    return a; /* since the loop exited, they are equal now. */
}

(我们还可以进行模运算来一次完成多个减法；这留作练习。)