Рекурсия в C confusion

Question

Я работаю над книгой, которая включает в себя главу, посвященную рекурсии в C. Он печатает 99 бутылочных песен в журнал. Вот код:

void singTheSong (int numberOfBottles) { 

    if (numberOfBottles == 0) { 
     printf("There are no more bottles left.\n"); 
    } else { 
     printf("%d bottles of bear 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", oneFewer); 

     singTheSong(oneFewer); 
    } 
} 

int main(int argc, const char * argv[]) 
{ 

    singTheSong(99); 
    return 0; 
} 

Выходные данные точно так же, как песня. У меня возникли проблемы с пониманием того, как переменная numberOfBottles меняет свое значение? Я вижу, что он вычитается одним в переменной oneFewer, но я не понимаю, как именно это работает. Мне кажется, что журнал будет читать «99 бутылок медведя на стене, 99 бутылок пива. Возьмите один, пропустите его, 98 бутылок пива на стене». повторяется, не опускаясь ниже 98. Я не уверен, как изменилось значение 10, и поэтому как oneFewer отслеживает количество бутылок. Еще один вопрос, является ли мое замешательство в отношении этой темы плохим признаком продолжения программирования? Я до сих пор его прибивал гвоздями.

Answer 1

Ключ здесь:

int oneFewer = numberOfBottles - 1; 
    singTheSong(oneFewer); 

Новый вызов singTheSong генерируется, где numberOfBottles составляет 98 вместо 99. Эта функция получает локальную копию numberOfBottles со значением 98.

Stack         numberOfBottles 
------------------------------------------------------ 
singTheSong       99 
    singTheSong       98 
    singTheSong      97 
     singTheSong      96 
     ...       ... 
      singTheSong     1 
      singTheSong    0 

К моменту, когда numberOfBottles достигает нуля, существует 100 вложенных вызовов singTheSong, сидящих на стеке. Наконец, функция возвращается без выполнения рекурсии, и все копии вверху стека, которые ожидали, будут возвращать по одному.

Answer 2

Возьмите лист бумаги и нарисуйте стек вызовов на каждый вызов, записав значение аргумента и обратный адрес (так что вы можете увидеть его unind). Это должно быть легче следовать.

Казнь всегда будет идти в else блок, за исключением последнего (базового случая с), где он будет идти в if блок, за исключением. Это будет означать, что число будет уменьшаться до тех пор, пока оно не достигнет 0.

Answer 3

Впервые singTheSong называется, numberOfBottles является 99.

Затем он вызывает singTheSong(numberOfBottles-1)99 - 1 = 98(), который будет затем вызвать singTheSong(numberOfBottles-1)с новым номером бутылок, т.е. 98 - 1 = 97.

Процесс повторяется до тех пор, пока не будет достигнут основной корпус.

Answer 4

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

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

Дело в рекурсии заключается в том, что оно вызывает много вызовов одной и той же функции в стеке вызовов.В этом случае, когда вы начинаете на 99, да, oneFewer = 98. Но затем, прежде чем закончить эту функцию, вы звоните singTheSong переходящим в oneFewer, то есть 98. И это будет вызывать singTheSong с oneFewer значения 97.

Это приведет к тому, что у вас будет 100 экземпляров одной и той же функции, собранной в стек вызовов. На 100-й песне вы печатаете «Осталось никаких бутылок», и ваша функция завершается. Затем функция для «1 бутылки» завершена, поэтому она выходит, позволяя завершить выполнение функции «2 бутылки» и т. Д. Полностью через стек вызовов, до тех пор, пока не будет завершена исходная функция.

Answer 5

После заявления «принять один вниз, передать его вокруг»,

singTheSong(oneFewer); 

вызывается с oneFewer, которая является переменной, которая содержит значение количества бутылок в этой конкретной итерации. Таким образом, numberOfBottles - это 99 вначале, затем oneFewer присваивается 98. Затем oneFewer = 98, передается на singTheSong. На этот раз аргумент, который называется numberOfBottles, имеет то же значение, что и один бит от предыдущей итерации. В этой итерации oneFewer получает значение 97, и этот цикл продолжается до тех пор, пока не будет достигнут базовый случай, который равен 1Fewer равным 0 и передается в singTheSong. singTheSong берет это значение и знает, что он достиг , если случай, поэтому он останавливается.

Answer 6

Дело в том, что функция singTheSong вызывает себя. Таким образом, функция main вызывает singTheSong (99). Эта функция печатает некоторые вещи, а затем вставляет 99 - 1 в переменную oneFewer, а затем снова вызывает singTheSong со значением oneFewer. Так что на этот раз значение, которое оно передано, не 99, оно равно 98.

Новая функция - это другой экземпляр singTheSong. Он ничего не знает о singTheSong, который был вызван раньше. Все, что он знает, это то, что ему было дано значение 98, и он должен распечатать некоторые вещи, вставить 98-1 в oneFewer, а затем вызвать singTheSong AGAIN.

К тому времени, когда программа опустится до 0, на самом деле будет 99 экземпляров singTheSong. Но когда он вызывается с нулем, вместо того, чтобы снова возвращаться, он просто печатает «Осталось никаких бутылок». Затем программа возвращается обратно через все 99 случаев и, наконец, заканчивается. 0 является, таким образом, базовым футляром , и очень важно, чтобы каждый рекурсивный алгоритм имел базовый случай, который был достигнут.

Если вы хотите это понять больше, попробуйте поместить printf («% d% d \ n», oneFewer, numberOfBottles); после рекурсивного вызова.

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