Почему рекурсивный вызов возврата выходит из стека без явного оператора возврата?

Мне была показана примерная программа для демонстрации рекурсии, которая выглядит так, как будто она не работает, но делает. Логика довольно понятна, но почему она работает, даже если вызов возвращенной функции не возвращается? Похоже, команда return вырывается из стека, даже если она не запрашивается. Является ли это стандартом языка или gcc? Я видел его с C и С++, скомпилированным с gcc в Windows и Linux.

#include <iostream>
#include <cstdlib>

using namespace std;

int isprime(int num, int i)
{
   if (i == 1) {
      return 1;
   }
   else {
      if (num % i == 0)
         return 0;
      else
         isprime(num, i-1); // should be returned
   }
}


int main(int argc, char** argv)
{
   int input = atoi(argv[1]);
   cout << input << "\t" << isprime(input, input/2) << "\n";
}

Ответ 1

Такие вещи работают только в том случае, если случайно возвращается возвращаемое значение в регистр, где его ожидает абонент. Это работает, только если это реализовано вашим компилятором как рекурсивная функция. Технически поведение undefined использует возвращаемое значение функции, которая не предоставляет ее.

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

Все эти шаблоны не будут работать, если возвращаемое значение будет размещено в некотором расположении стеков (рекурсивных) вызывающих абонентов.

В любом случае все это должно быть зафиксировано любым современным компилятором и дать вам предупреждение. Если это не так, у вас нет хорошего компилятора, или вы используете слишком оборонительные параметры командной строки.

Новый год особенный: в реальном мире код, подобный этому (с return), даже не будет реализован как рекурсивная функция. С небольшими усилиями вы найдете итеративный вариант этой функции, и любой современный достойный компилятор должен также найти его, если вы попросите максимальную оптимизацию.

Ответ 2

Многое здесь зависит от того, что вы подразумеваете под "это работает"?

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

Я ожидаю увидеть предупреждения компилятора, сообщающие вам, что возможные пути управления могут не возвращать значение на С++ в любом случае. В результате действия undefined см. Этот вопрос: не возвращает значение из функции возврата не-void

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

... но поскольку поведение undefined, значение, которое фактически выводится, скорее всего, будет мусором. Если вы видите 0 и 1, согласующиеся с штрихами в качестве входных данных, тогда ничего себе.

Если вы думаете, что это работает, я бы посмотрел на тестирование более широко с разными значениями.

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

Ответ 3

Я могу точно объяснить, что происходит:

Вызывается функция, и она возвращается обратно в себя до тех пор, пока она не вернется к возврату ни по модулю (возврат 0), ни к концу рекурсии (возврат 1). На этом этапе функция повторно возвращается к вызывающему, который is_prime. Но в исполняемой функции больше нет кода, поэтому он немедленно возвращается без каких-либо дальнейших действий.

Однако вы можете легко сломать это, например, добавить printf("Done for %d, %d\n", num, i); за вызов is_prime() [не обязательно в if-statement]. Или добавление объекта С++, который создается и уничтожается при входе/выходе функции, в качестве другого примера.

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

Ответ 4

Разве вы не забываете о возвращении? Для нормальной рекурсии вам нужно вернуть значение до isprime(num,i-1);.

Я думаю, это даже должно дать предупреждение компиляции, если вы скомпилируете это с помощью строгих правил, потому что функция должна всегда возвращать int, теперь это не так (по крайней мере, если ваш компилятор не исправляет это).