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

Question

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

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

Answer 2

Думайте об этом так.

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

Answer 3

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

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

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

Answer 4

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

gcc -o test -g test.c

Затем запустите с GDB, как это.

gdb test

Затем, чтобы начать, наберите

start

Который прерывается при первом вызове в основной функции. Тип

step

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

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

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)".

Теперь, когда вы достигнете n (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.

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

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

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