Кто-нибудь может объяснить мне этот вывод? - PullRequest
Новая
       23

Кто-нибудь может объяснить мне этот вывод?

1 голос
/ 19 июня 2011

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

Для этого я подумал о следующем простом примере: 

#include <iostream>
#include <cstdlib>

int foo(int x);
int bar(int x);


int foo(int x)
{
    return bar(x + 1);
}

int bar(int x)
{
    return foo(x - 1);
}

int main(int argc, char **argv)
{
    if (argc > 1)
        std::cout << "The value is: " << foo(atoi(argv[1])) << std::endl;

    return 0;
}

Интересно, что это на самом деле выведет на печатьабсолютно ничего, если вы скомпилируете это с g ++.Скомпилируйте его с любым ключом -O, и он попадет в бесконечный цикл.

Мысли?Возможно, это ошибка компилятора, или это следует ожидать?Я бы подумал, что в случае оптимизации -O он понял бы, что foo (x) и bar (x) возвращают только x.

Я не ожидал, что он действительно "оптимизирует" вызов иполностью игнорируйте вывод «Значение» на стандартный ввод.

Редактировать: я скомпилировал это как просто g ++ source.cpp (-O1 / 2/3), в Cygwin, используя GCC 4.5.0.Версии -OX фактически зацикливаются без переполнения стека.

Ответы [ 3 ]

2 голосов
/ 19 июня 2011

Поскольку вы не указали, на каком C ++ вы работаете, я отвечу на C ++ 0x:

Это на самом деле неопределенное поведение в C ++ 0x .

Я не могу полностью объяснить поведение, если вы используете C ++ 03, но, поскольку ваш стек в конечном итоге переполнится, вы по-прежнему находитесь в сфере поведения, зависящего от реализации. Ожидать, что здесь произойдет что-то вменяемое, - глупое поручение.

1 голос
/ 19 июня 2011

С математической точки зрения, f (x) = b (x + 1) и b (x) = f (x - 1) недостаточно для определения f и b .Одним из возможных решений является f (x) = x и b (x) = x - 1 , а другое - f (x) = 0 и g (x) = 0 (и существует бесконечно много других способов).Математически, вопрос о том, что функция должна возвращать, не имеет ответа.С вычислительной точки зрения ситуация еще хуже, потому что, в конце концов, вы не определяете математические функции, вы указываете, как должно выполняться вычисление.foo(x - 1) означает «выполнить вычисления, указанные в функции foo(), когда мы передаем значение x - 1 в качестве параметра», и аналогично для bar(x + 1).Поэтому, когда каждая функция безоговорочно говорит, что должна быть вызвана другая функция, вы указали, что хотите, чтобы выполнялась бесконечная рекурсия.Как уже упоминали другие, некоторые языки (или языковые версии) рассматривают это как четко определенную ситуацию (где желаемый результат - зависание программы), в то время как другие рассматривают это как неопределенную ситуацию (т. Е. Компилятор может делать все что угодно).

0 голосов
/ 19 июня 2011

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

Компилятор не может просто оптимизировать удаленную рекурсию.

...