Я играл с рекурсией и выполнял эту простую функцию. Я предполагал, что он выведет 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;
}
Как говорит Майкл Барр в комментариях, если вы хотите посмотреть, что происходит, скомпилируйте с включенными символами отладки, например:
gcc -o test -g test.c
Затем запустите с помощью gdb.
gdb test
Затем, чтобы начать все, введите
start
Что происходит при первом вызове основной функции. Тип
step
чтобы перейти к следующей строке в коде, и с этого момента просто нажмите Enter, чтобы повторить последнюю команду. Если вы счастливы, введите continue, чтобы остановить переход. Вы увидите значения и оцениваемые строки на каждом этапе, которые подтвердят приведенные выше ответы.
Надеюсь, что предоставит некоторую полезную информацию.
Функция 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);
Перепишите свой код следующим образом:
int rec(int n){
if(n > 0)
{
int retval = rec(n -1);
printf("%d\n", retval);
}
return n;
}
Означает ли это, почему 0 печатается сначала до 9?
Поскольку вы создаете 9 ambients 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), вы вызываете другую печать и еще раз сказать "разрешить 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;
}
В общем, рассмотрим часть кода. Мы говорим, что существует прямая связь между итерационными и рекурсивными решениями, так что любое решение можно записать итеративно и наоборот. Однако в некоторых случаях легче выразить алгоритм рекурсивно (например, Башня Ханоя). В случае с кодом выше эквивалент будет конструкцией цикла цикла.
Это может быть реализовано как функция следующим образом:
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 />
}
Примечание. Это можно расширить с помощью указателей функций.