Эта рекурсивная функция озадачивает меня, что продолжается?
Я играл вокруг с рекурсией и сделал эту простую функцию. Я предполагал, что это распечатает 9-0 к stdout, но, это печатает 0-9. Я не вижу, как это происходит вообще.
int main()
{
rec(10);
return 0;
}
int rec(int n){
if(n > 0)
printf("%d\n", rec(n -1));
return n;
}
6 ответов
Как говорит Майкл Берр в комментариях, если вы хотите увидеть, что происходит, скомпилируйте с включенными отладочными символами, например:
gcc -o test -g test.c
Затем запустите с gdb вот так.
gdb test
Затем, чтобы начать работу, введите
start
Который прерывается при первом вызове функции main. Введите
step
, чтобы перейти к следующей строке кода, и с этого момента просто нажмите клавишу ВВОД, чтобы повторять последнюю команду. Если вы довольны, введите continue , чтобы не переходить дальше. Вы увидите значения и оценочные строки на каждом этапе, которые подтвердят приведенные выше ответы.
Надеюсь, что здесь есть полезная информация.
Давайте перепишем ваш код следующим образом:
int rec(int n){
if(n > 0)
{
int retval = rec(n -1);
printf("%d\n", retval);
}
return n;
}
Понятно ли, почему 0 печатается первым перед 9?
Поскольку вы создаете 9 окружающих 9> 8> 7> 6> 5> 4> 3> 2> 1> 0 , теперь эти окружающие среды обрабатываются так же, как a ( b (c (d (e (f (g ()))))) , переходя от самого глубокого к первому.
Помните, что когда вы делаете это printf ("% d", n (m)); , вы на самом деле ничего не печатаете, вы говорите «распечатайте результат n (m)» затем, когда он пытается разрешить n (m), вы вызываете другой print и еще раз говорите «разрешите n (m-1)».
Теперь, когда вы дойдете до n (0), он вернет 0, который будет напечатан последним вызовом printf , поэтому он напечатает 0, затем 1 .. 9.
int main()
{
rec(10);
return 0;
}
int rec(int n){
if(n > 0)
printf("%d\n", rec(n -1));
return n;
}
В общем, рассмотрите какой-нибудь фрагмент кода. Мы говорим, что существует прямая связь между итеративными и рекурсивными решениями, так что любое решение может быть записано итеративно и наоборот. Однако в некоторых случаях кажется, что проще выразить алгоритм рекурсивно (например, Ханойская башня). В случае приведенного выше кода эквивалентом будет конструкция цикла for.
Это может быть реализовано как функция следующим образом:
void _for(int i, int n)
{
if( i >= n ) return; // TERMINAL<br />
// some expression (ie. printf("%d\n",i);)<br />
_for(i+1,n) // RECURSION<br />
}
Обратите внимание, это может быть расширено с помощью указателей функций.
Функция rec в строке printf оценивается перед самой printf . Таким образом, самый глубокий экземпляр функции rec печатается первым .
Думайте об этом так.
rec(10)
rec(9)
rec(8)
rec(7)
rec(6)
rec(5)
rec(4)
rec(3)
rec(2)
rec(1)
rec(0)
Начинаем разматывать
printf("%d\n", 0);
printf("%d\n", 1);
printf("%d\n", 2);
printf("%d\n", 3);
printf("%d\n", 4);
printf("%d\n", 5);
printf("%d\n", 6);
printf("%d\n", 7);
printf("%d\n", 8);
printf("%d\n", 9);