Когда используются рекурсивные вызовы функций, когда использовать 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)?

Answer 1

Почему там требуется возврат, учитывая, что в обоих случаях я вызываю функцию gcd (arg1, arg2)?

По той же причине, что требуется в любой другой раз, когда вы вызываетефункция и желание вернуть значение, которое было возвращено этим вызовом функции;потому что при вызове он только вызывает его и ничего не делает с результирующим значением.

Я не понимаю, когда использовать return при использовании рекурсивных вызовов функций.

Используйте return для рекурсивного вызова, всякий раз, когда вы будете использовать return для любого другого вызова функции - т.е. когда и потому что этот вызов возвращает значение, которое вы хотите вернуть на этот раз.

Представьте, что у нас есть

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

И затем вместо рекурсивных вызовов мы делегируем часть работы этому:

/* 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 достигается при любых обстоятельствах, и это нарушает цикл.)

Я предполагаю, что мне не нужно идтинад математической теорией;и также я предполагаю, что ясно, почему return необходим для gcd2 результатов.

Но это на самом деле не имеет значения как делегируется работа;если gcd является функцией, которая правильно вычисляет GCD, и gcd2 также является таковой, то вызов gcd2 может быть заменен вызовом gcd. В этом секрет - рекурсивный вызов функции на самом деле не отличается от обычного вызова. Просто учитывая эту возможность, требуется более четкое понимание того, как работает вызов функции и что она на самом деле делает.

---

Конечно, также возможно хорошо использовать оригинальный цикл while- вычитая как можно больше до выполнения рекурсии. Это может выглядеть так:

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. */
}

(И мы также могли бы выполнить арифметику по модулю для достижениянесколько вычитаний одновременно; это оставлено как упражнение.)

Answer 2

Первая функция gcd «пытается» вычислить gcd, но в конце всегда возвращает a без изменений.

Вторая функция gcd рекурсивно вычисляет gcd, и каждый вызов возвращает gcd.