Понимание рекурсии в примере с бутылкой пива

Question

Я занимаюсь рекурсией в C самостоятельно, и я нашел этот пример онлайн. Однако есть одна вещь, которую я не понимаю.

void singSongFor(int numberOfBottles) 
{ 
if (numberOfBottles == 0) { 
    printf("There are simply no more bottles of beer on the wall.\n\n"); 
} 
else { 
    printf("%d bottles of beer on the wall. %d bottles of beer.\n", 
      numberOfBottles, numberOfBottles); 
    int oneFewer = numberOfBottles - 1; 
    printf("Take one down, pass it around, %d bottles of beer on the wall.\n\n", 
      oneFewer); 
    singSongFor(oneFewer); // This function calls itself! 

    // Print a message just before the function ends 
    printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", 
      numberOfBottles); 
    } 
}  

Затем я использую основной метод как таковой:

int main(int argc, const char * argv[]) 
{ 
    singSongFor(4); 
    return 0; 
} 

И выход как таковой:

4 бутылки пива на стене. 4 бутылки пива. Возьмите один, пропустите его, 3 бутылки пива на стене.

3 бутылки пива на стене. 3 бутылки пива. Возьмите один, пропустите его, 2 бутылки пива на стене.

2 бутылки пива на стене. 2 бутылки пива. Возьмите один, пропустите его, 1 бутылку пива на стене.

1 бутылки пива на стене. 1 бутылка пива. Возьмите один, пропустите его, 0 бутылок пива на стене.

На стене просто нет бутылок пива.

Положить бутылку в переработку, 1 пустую бутылку в мусорное ведро.

Положить бутылку в переработку, 2 пустые бутылки в мусорном ведре.

Положить бутылку в утилизацию, 3 пустые бутылки в мусорное ведро.

Положить бутылку в рециркуляцию, 4 пустые бутылки в мусорном ведре.

Я понимаю, первая часть очень хорошо, пока я не пришел к «Там просто нет больше бутылок пива на стене. Я не понимаю, потом как переменное число бутылок увеличивается от 1 до 4.

Answer 1

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

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

4 bottles of beer on the wall... 
    3 bottles of beer on the wall... 
    2 bottles of beer on the wall... 
     1 bottles of beer on the wall... 
     There are simply no more bottles of beer on the wall. 
     Put a bottle in the recycling, 1 empty bottles in the bin. 
    Put a bottle in the recycling, 2 empty bottles in the bin. 
    Put a bottle in the recycling, 3 empty bottles in the bin. 
Put a bottle in the recycling, 4 empty bottles in the bin. 

Теперь каждая строка, начинающаяся в том же столбце, записывается из одного и того же вызова функции. Вы видите, как количество бутылок и рециркуляция coindice? Это потому, что обе используют одну и ту же переменную: numberOfBottles.

Answer 2

Операция утилизации запускается после возврата рекурсивного вызова.

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

Answer 3

С рекурсией вы можете думать обо всем, прежде чем рекурсивный вызов будет представлять собой прямой цикл, и все после вызова как обратный цикл.(Рекурсия хвоста - вызов функции снова в конце функции - часто оптимизируется компилятором в простой прямой цикл.)

Как это работает, аргументы для каждой старой функции помещаются в стек и выталкивается, когда все возвращается. Помните, что стек является последним, первым вышел. Так как вы начинаете с 4, он нажимает 4, затем 3, затем 2, затем 1. Когда функции возвращаются, стек начинает разматываться, поэтому вы снова видите аргументы в обратном порядке: 1,2,3,4.

Answer 4

Меньшие бутылки пива (и их соответствующая рециркуляция) находятся во внутренних функциях. Ваше дерево функций выглядит так:

4 bottles of beer on the wall. 4 bottles of beer. Take one down, pass it around, 3 bottles of beer on the wall. 
| 3 bottles of beer on the wall. 3 bottles of beer. Take one down, pass it around, 2 bottles of beer on the wall. 
| | 2 bottles of beer on the wall. 2 bottles of beer. Take one down, pass it around, 1 bottles of beer on the wall. 
| | | 1 bottles of beer on the wall. 1 bottles of beer. Take one down, pass it around, 0 bottles of beer on the wall. 
| | | | There are simply no more bottles of beer on the wall. 
| | | Put a bottle in the recycling, 1 empty bottles in the bin. 
| | Put a bottle in the recycling, 2 empty bottles in the bin. 
| Put a bottle in the recycling, 3 empty bottles in the bin. 
Put a bottle in the recycling, 4 empty bottles in the bin. 

Answer 5

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

Answer 6

Причина, по которой работает таким образом, что каждый вызов singSongFor() где numberOfBottles составляет более 1, в свою очередь рекурсивный вызов singSongFor() до numberOfBottles не равно 0. В этот момент printf("There are simply no more bottles of beer on the wall.\n\n") достигается и что функция будет закончить, переходя к вызывающая функция, которая будет иметь аргумент из 1 пройденного, который затем достигает printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles); и сам завершается, возвращаясь к singSongFor(2) ... и так далее, пока вы не вернетесь к своему первоначальному номеру 4 в этом случае.

Answer 7

Просто простая картина explaines: