Смутно о рекурсии в C

Ответ 1

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

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

void SingSongFor4(){

        printf("4 bottles of beer on the wall. 4 bottles of beer.\n");

        printf("Take one down, pass it around, 3 bottles of beer on the wall.\n\n");

        SingSongFor3();

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

void SingSongFor3(){

        printf("3 bottles of beer on the wall. 3 bottles of beer.\n");

        printf("Take one down, pass it around, 2 bottles of beer on the wall.\n\n");

        SingSongFor2();

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

void SingSongFor2(){

        printf("2 bottles of beer on the wall. 2 bottles of beer.\n");

        printf("Take one down, pass it around, 1 bottles of beer on the wall.\n\n");

        SingSongFor1();

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

void SingSongFor1(){

        printf("1 bottles of beer on the wall. 1 bottles of beer.\n");

        printf("Take one down, pass it around, 0 bottles of beer on the wall.\n\n");


        printf("Put a bottle in the recycling, 1 empty bottles in the bin.\n");
    }
}

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

    // We could sing 99 verses, but 4 is easier to think about
    SingSongFor4();

    return 0;
}

Я надеюсь, что очевидно, что каждая функция печатает пару строк, вызывает следующую функцию, затем печатает другую строку. Каждая вызываемая функция делает это, в свою очередь, так, например, печатаются 2 строки для SingSongFor4(), затем вызывается SingSongFor3. Это печатает две строки, затем вызывает SingSongFor2(), который печатает свои строки и так далее. SingSongFor1() не вызывает никаких других функций, поэтому он печатает все три строки, а затем возвращается к SingSongFor2(), который завершается и т.д. вверх по цепочке. Во всех случаях вы получаете 8 строк X bottles on the wall/take one down по мере того, как вы выполняете функцию "down", а затем 4 строки "Положите бутылку в корзину", когда вы возвращаете "вверх" в обратном направлении.

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

Обычно эта контекстная информация содержится в специальной структуре данных, называемой стеком. Он называется стек, потому что вы складываете вещи один поверх другого, а затем удаляете их по одному из "верхнего". Каждый кадр стека содержит контекст одного вызова функции: параметры - в вашем случае numberOfBottles; локальные переменные - oneFewer; и информация о том, какой оператор должен выполняться, когда функция заканчивается или возвращается. Когда функция вызывается, кадр, соответствующий этому вызову, помещается в стек, и текст функции выполняется. Когда он заканчивается, кадр исчезает, и выполнение возобновляется в вызывающей функции в точке, где она была остановлена ​​(которая была сохранена в стеке с выталкиванием стека для этой цели). Он возобновляется с использованием нового "верхнего" кадра стека для контекста.

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

Ответ 2

3 бутылки:

SingSong(3):
 PRINT 2 LINES
 SingSong(2):
     PRINT 2 LINES
     SingSong(1):
          PRINT 2 LINES
          SingSong(0):
               PRINT 1 LINES
          PRINT RECYCLE LINE
     PRINT RECYCLE LINE
 PRINT RECYCLE LINE

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

Ответ 3

Рекурсивные вызовы функций сложены. Итак, это выглядит примерно так:

SingSongFor(4)
  |
  v
SingSongFor(3)
  |
  v
SingSongFor(2)
  |
  v
SingSongFor(1)
  |
  v
SingSongFor(0)

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

Ответ 4

После строки

 SingSongFor(oneFewer); // This function calls itself

У вас есть printf i.e.

 printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",numberOfBottles);

Так вот что делает программа. Значение numberOfBottles, которое хранится в стеке.

Ответ 5

Все в порядке. Когда вы достигнете окончательного сообщения There are simply no more bottles of beer on the wall., ваша программа вернется к точке, где она была вызвана (она вызывается в функции SingSongFor с аргументом 1). Затем печатает сообщение Put a bottle in the recycling, 1 empty bottles in the bin. и возвращает к предыдущему вызову функцию SingSongFor с аргументом 2. И как это до 4.

Ответ 6

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

В настоящее время

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

Что вы хотите:

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

Таким образом, вы получите ожидаемый результат, и THEN произойдет следующий переход.

Ответ 7

Если я понимаю, что вы хотите только распечатать общее количество в корзине один раз, когда рекурсия завершается, самым простым решением является использование функции wrapper (или вспомогательного) для вызова SingSonfFor. Используя оболочку, вы сохраняете исходный numberOfBottles как счетчик для повторного использования, в то время как каждый бит рекурсии уменьшает число на единицу. Пример:

#include <stdio.h>
#include <stdlib.h>

void SingSongFor (int numberOfBottles){

    if (!numberOfBottles)
        return;

    int oneFewer = numberOfBottles - 1;

    printf (" %d bottles of beer on the wall. %d bottles of beer.\n", 
            numberOfBottles, numberOfBottles);

    printf (" Take one down, pass it around, %d bottles of beer on the wall.\n\n", 
            oneFewer);

    if ((oneFewer) == 0)
        printf (" There are simply no more bottles of beer on the wall.\n\n");
    else 
        SingSongFor (oneFewer); // This function calls itself!
}

void ss_helper (int numberOfBottles)
{
    SingSongFor (numberOfBottles);

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

    if (numberOfBottles >= 6)
        printf ("\n Now go sober up you lush...\n\n");
}

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

    // We could sing 99 verses, but 4 is easier to think about
    int coldbeers = (argc > 1) ? atoi (argv[1]) : 4;
    // SingSongFor (coldbeers);
    ss_helper (coldbeers);

    return 0;
}

выход:

$ ./bin/beersong
 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, 4 empty bottles in the bin.

Ответ 8

В вашем коде:

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

Вызов функции SingSongFor не возвращается, пока не завершит (и все дочерние функции, которые он вызвал, также завершили).

Таким образом, строка printf вынуждена ждать, пока все нижние вызовы SingSongFor не закончатся, прежде чем они будут запущены.

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

Этот процесс объясняет, почему вызовы функций создают стек состояний выполнения, причем каждая запись стека содержит локальные значения, которые понадобятся при возобновлении выполнения на этом уровне (в этом случае просто numberOfBottles, и адрес памяти следующей команды, который ожидает выполнения).

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