Поток рекурсии на языке c и как печатается вывод

Question

Какова стоимость печати?

Я знаю, что рекурсия вызывает себя снова и снова. По моему мнению, функция должна возвращать пустой, так как функция вызывается перед печатью Как работает printf?

recur(int i)
{
  if(i<0)
    return 0;
  recur(--i);
  printf("%d",i);
  recur(--i);
}

main()
{
  recur(2);
}

The output of this program is 
-1
0
1
-1

Может кто-нибудь объяснить, как это работает?

Answer 1

Вместо recur(--i), пожалуйста, recur(i-1)

С --i оно действительно уменьшится i, и поэтому в дальнейшем printf будет видно (неправильно).

Например, если i равно 0, а вы делаете recur(--i), фактическое значение уменьшится с i до -1, а затем вызовет recur(). И printf напечатает -1 позже.

С recur(i-1) и i в качестве 0 будет вызываться с -1 в качестве аргумента, но фактическое значение i не изменится.

Answer 2

ТАКЖЕ РАССМОТРЕНО

Вы используете переменную в качестве автоматической переменной, значение автоматической переменной ограничено панатезисом, поэтому программа напечатает значение i, доступное в рамках парантеза вкоторый поток управления находится в настоящее время

Answer 3

Чтобы понять, что происходит, вы должны понять, как работает рекурсия. Каждая рекурсивная функция требует условия тестирования для прерывания рекурсии и рекурсивного вызова. У вас есть if (i < 0) в качестве условия тестирования, а затем у вас два рекурсивных вызова с printf между ними.

Так как же это работает?

Вы можете думать о рекурсии и сворачивании до тех пор, пока не сработает условие выхода, а затем раскрутиться, когда возвратятся рекурсивные вызовы. Давайте посмотрим, как это работает здесь.

Рекурсия

Когда вы начнете с recur(2) в main, по какому пути логика перейдет к условию выхода?

Если вы упростите функцию и сконцентрируетесь на том, что происходит до того, как будет выполнено условие вашего теста, вы получите нечто похожее на:

void recur (int i) {
    if (i < 0)
        return;
    recur (--i);
    /* comes after return */
}

Давайте пройдем через это. При первом вызове i = 2, поэтому --1 pre decriment происходит, делая i = 1, recur (1). Следующий звонок i = 0, recur (0) вызывается снова. Наконец, i = -1, и появляется первый recur(-1), поэтому if (i < 0) выполняется и вызывается return.

Что теперь? - Разматывать ...

Посмотрите на приведенную выше укороченную функцию. Когда вы return, вы возвращаетесь с последнего вызова на recur(--i), поэтому управление теперь передается следующей команде после первой recur(-1) (показанной как /* comes after return */ выше). Каковы следующие команды в полной функции?

    printf("%d\n", i);
    recur (--i);

Каково было значение i, когда это произошло впервые? (подсказка: -1).

Итак, printf называется, и что дальше? Ваш второй recur(--i). Там i = -2, if (i < 0) return; срабатывает, и вы выходите из второго recur(-2) - нет команды, которая следует, и этот вызов функции теперь завершен.

Теперь управление переходит к предыдущему вызову, где i теперь 0, вызывается printf, а во второй recur(--i) вводится i = -1, который просто снова нажимает return и вы раскручиваете один На следующем уровне i = 1 возвращается снова после первого вызова recur(--i), выводится 1.

Второй recur(--i) вызов вводится там, где после декремента i = 0, и теперь вы снова рекурсируете в первый, где i = -1 снова запускает return, что заставляет контроллер перейти к printf с последним -1 печать.

Теперь вы вернетесь ко второму recur(--i) с i = -2, вызвав return и завершив вызов функции и рекурсию.

Итак, если вы вернетесь к управлению своей рекурсивной функцией двумя рекурсивными вызовами и посмотрите на каждый раз, когда достигнуто printf, вы получите -1, 0, 1, -1.

Все еще думаете, что рекурсивные функции с несколькими рекурсивными вызовами - это хорошая идея?

(если вы продавец Аспирина - иначе их лучше избегать, если только это не единственный разумный вариант, который у вас есть)

Единственный способ справиться с чем-то подобным - это (1) подружиться с вашим отладчиком и пошагово пройти по коду, сохраняя блокнот, в который был введен вызов, или (2) скопировать и вставить функцию вниз по странице, отслеживая состояние рекурсивного вызова на каждом уровне, и выполняйте его пошагово.

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

Answer 4

Когда функция вызывается с аргументом X >= ноль, вы получите следующие строки:

recur(X-1)
print X-1
recur(X-2)
return

Когда функция вызывается с аргументом X < ноль, будет выполняться только эта строка:

return

Теперь, если вы напишите вызовы функций с некоторыми отступами для каждого уровня вызовов, вы получите:

recur(2)
        recur(1)
                recur(0)
                        recur(-1)
                                return
                        print -1
                        recur(-2)
                                return
                        return
                print 0
                recur(-1)
                        return
                return
        print 1
        recur(0)
                recur(-1)
                        return
                print -1
                recur(-2)
                        return
                return
        return
return

Удаление всего, кроме печати, дает:

                        print -1
                print 0
        print 1
                print -1

Итак, вывод:

-1
0
1
-1

Answer 5

Проблема в том, что вы вызываете свою функцию до того, как распечатываете значение.

recur(int i)
{
if(i<0)
    return 0;
recur(--i);
printf("%d",i);
recur(--i);
}

Вы вызываете recur(2) в вашей функции main, первая if(i<0) не возвращает 0, потому что i=2. Затем ваша функция recur вызывается со значением 1 recur(1)

if(i<0) в этом случае также не возвращает 0, потому что i=1, чем ваша функция recur(0), вызывается с 0.

if(i<0) по-прежнему не возвращает 0 из-за i=0, и ваша функция вызывается с помощью recur(-1).

Тогда вы if(i<0) returns 0 потому что i=-1.

Теперь мы начинаем print() из значений, которые мы дали функции ранее. Это было print(-1), потому что это было последнее значение, которое имела наша функция.

Затем мы снова вызываем recur с recur(-2), а if возвращает 0.

Тогда мы print(0), потому что это было второе введенное нами значение, равное 0.

Затем мы вызываем recur с recur(-1) и if(i<0) возвращает 0.

Это продолжается для следующих значений.

Для будущих проблем я бы порекомендовал вам использовать отладчик. Отладчик GDB, например.

Вот как начать работу с gdb: GDB Start guid

Надеюсь, это поможет вам.

Answer 6

Когда вы звоните recur(2);, то в этот момент

recur(--i);

recur(1) вызывается, и затем, когда он снова достигает этой точки, вызывается recur(0);, а затем в этой точке снова вызывается recur(-1);. Вызов recur(-1); немедленно возвращается, потому что if(i<0) return 0;.

Вызов recur(0);, где i теперь равен -1, затем печатает и возвращает (снова делает recur(--i);, но на данный момент это -2). Далее, вызов recur(1) (где i равен 0 сейчас) печатает, и он также набирает recur(1), что возвращает.

Наконец, исходный вызов recur(2); (где i равен 1) печатает и вызывает другой recur(0);, что, как мы видели, приводит к печати -1. Это приводит к выводу -101-1, или, если вы добавляете новую строку для каждого отпечатка, вывод, который вы видите.

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

int main()
{
    recur(2);
    return 0; // return value of 0 indicates successful program execution
}

и измените подпись recur(int i) на void recur(int i) и return 0; на return;.

по моему мнению, функция должна возвращать пустой, так как функция вызывается перед печатью. как работает printf?

Подводя итог, он работает, потому что не все рекурсивные вызовы выполняют дополнительные рекурсивные вызовы. Они выполняют рекурсивные вызовы только при определенных условиях, и если они не выполняют этот рекурсивный вызов, они завершаются в какой-то момент, позволяя функции, вызвавшей его, продолжаться.