Эта рекурсивная функция меня озадачивает, что происходит?

Question

Я играл с рекурсией и выполнял эту простую функцию. Я предполагал, что он выведет 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; 
} 

Answer 1

Как говорит Майкл Барр в комментариях, если вы хотите увидеть, что происходит, компилировать с символами отладки включен, например:

gcc -o test -g test.c 

Затем запустите gdb.

gdb test 

Затем, чтобы начать вещи, идущие, тип

start 

нарушающий при первом вызове в основной функции. Тип

step 

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

Надеюсь, что предоставит некоторую полезную информацию.

Answer 2

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

Answer 3

Подумайте об этом.

rec(10) 
rec(9) 
rec(8) 
rec(7) 
rec(6) 
rec(5) 
rec(4) 
rec(3) 
rec(2) 
rec(1) 
rec(0) 

Start разматывать

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); 

Answer 4

Давайте перепишем код, как это:

int rec(int n){ 
     if(n > 0) 
     { 
       int retval = rec(n -1); 
       printf("%d\n", retval); 
     } 
     return n; 
} 

Есть ли понять, почему 0 печатается первым, прежде чем 9?

Answer 5

Поскольку вы создаете 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), вы вызываете другую печать и говоря еще раз «разрешить n (m-1)».

Теперь, когда вы дойдете до п (0) вернет 0 для печати последним вызовом printf, поэтому он печатает 0, то 1 .. 9.

Answer 6

int main() 
{ 
     rec(10); 
     return 0; 
} 

int rec(int n){ 
     if(n > 0) 
       printf("%d\n", rec(n -1)); 
     return n; 
} 

В общем, рассмотрим какую-нибудь кода. Мы говорим, что существует прямая связь между итерационными и рекурсивными решениями, так что любое решение можно записать итеративно и наоборот. Однако в некоторых случаях легче выразить алгоритм рекурсивно (например, Башня Ханоя.) В случае кода выше эквивалент будет конструкцией for loop.

Это может быть реализован в виде функции следующим образом:

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

Заметим, что это может быть расширена с помощью указателей на функции.