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

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

Ответы

Ответ 1

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

gcc -o test -g test.c

Затем запустите с помощью gdb.

gdb test

Затем, чтобы начать все, введите

start

Что происходит при первом вызове основной функции. Тип

step

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

Перепишите свой код следующим образом:

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

Означает ли это, почему 0 печатается сначала до 9?

Ответ 5

Поскольку вы создаете 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.

Ответ 6

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

Примечание. Это можно расширить с помощью указателей функций.