Блог

Я нахожусь в главе 9 C Primer Plus, где автор представил то, что называется рекурсией. Я смущен выводом примера программы, который он представил. Нужна помощь от ваших ребят.

Ниже приведен код

  #include <stdio.h>
 void up_and_down(int);
 int main(void)
 {
    up_and_down(1);
    return 0;
 }
 void up_and_down(int n)
 {
    printf("Level %d: n location %pn", n, amp;n); // 1
    if (n < 4)
       up_and_down(n 1);
    printf("LEVEL %d: n location %pn", n, amp;n); // 2
 } 
 

Вот результат

1. Уровень 1: n местоположение 0x0012ff48
2. Уровень 2: n местоположение 0x0012ff3c
3. Уровень 3: n местоположение 0x0012ff30
4. Уровень 4: n местоположение 0x0012ff24
5. УРОВЕНЬ 4: n местоположение 0x0012ff24
6. УРОВЕНЬ 3: n местоположение 0x0012ff30
7. УРОВЕНЬ 2: n местоположение 0x0012ff3c
8. УРОВЕНЬ 1: n местоположение 0x0012ff48

Никаких проблем до уровня 4, где n = 4. На этом этапе оператор if завершается ошибкой, а затем выполняется вторая функция printf . После второй распечатки printf Level 4: n location 0x0012ff24 разве элемент управления не должен передаваться обратно return 0 в основную функцию? Почему второй printf продолжает выводить остальные три n переменных и, в частности, в обратном направлении.

Автор объясняет, что это связано

управление передается обратно функции, которая его вызвала (вызов уровня 3). Последним оператором, выполненным при вызове уровня 3, был вызов уровня 4 в операторе if. Следовательно, уровень 3 возобновляется со следующим оператором, который является оператором печати # 2. Это приводит к печати УРОВНЯ 3. Затем Level3 завершается, передавая управление на уровень 2, который выводит УРОВЕНЬ 2, и так далее.

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

Почему второй printf продолжает печатать 3,2 и 1? И особенно в таком порядке. Означает ли второй printf вывод всех n переменных? Какова логика поведения второго printf .

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

Нет, не должно. Позвольте мне попытаться, ну, убедить вас аналогией.

Предположим, у вас есть четыре функции: up_and_down_1() , up_and_down_2() , up_and_down_3() и up_and_down_4() , каждая из которых вызывает следующую внутри.

Теперь, если я нахожусь в теле up_and_down_1() , и я вызываю up_and_down_2() , и эта функция завершается (неважно, что она делает) — control возвращается к следующей строке up_and_down_1() после вызова to up_and_down_2() . Вот как работают вызовы функций в C (смотрите Также Здесь для подробностей низкого уровня).

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

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

Что такое стек вызовов и фреймы стека в рекурсивном программировании?

Поскольку рекурсия не является особенной, и когда функция возвращает (любую функцию; включая рекурсивные вызовы функций), выполнение начинается с того места, где оно было остановлено до вызова функции. Это означает, что когда вы находитесь внутри третьего уровня, он выполняет рекурсивный вызов четвертого уровня. Когда возвращается вызов четвертого уровня, выполнение возвращается туда, где оно было до вызова рекурсивной функции: на третий уровень.

Забудьте о рекурсии на секунду. Допустим, у вас есть ваша пользовательская функция, которая содержит вызов printf , и эта пользовательская функция вызывается изнутри main . Когда printf возвращается, куда возобновляется выполнение? main или внутри вашей пользовательской функции, где она остановилась? Последнее. Ваша функция должна завершить выполнение кода после printf вызова, а затем, когда она завершится, выполнение вернется обратно main . То же самое с рекурсивными функциями.

Его объяснение излишне сложно. Когда вы вызываете функцию, вы выполняете любой код, который там есть. Когда функция вызывает другую функцию, она выполняет код, а затем возвращается к тому, где она была. Вы можете, ради этого примера, представить это как вставку содержимого с замененными аргументами, поэтому up_and_down(1) становится:

 printf("Level %d: n location %pn", n, amp;n); // n = 1
if (n < 4) { // n = 1
    printf("Level %d: n location %pn", n, amp;n); // n = 2
    if (n < 4) // n = 2
       ... paste again with n = 3
    printf("LEVEL %d: n location %pn", n, amp;n); // n = 2
}
printf("LEVEL %d: n location %pn", n, amp;n); // n = 1
 

Это в основном так:

 print("enter 1")
if (...)
  print("enter 2")
  if (...)
    print("enter 3")
    if (...)
      print("enter 4")
      // if evaluates to false here, so we dont go deeper
      print("exit 4")
    print("exit 3")
  print("exit 2")
print("exit 1")
 

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

Каждый вызов функции «блокируется» до тех пор, пока вызванная функция не вернется.

Уровень 1 вызовет уровень 2 до того, как уровень 1 достигнет второго printf . Однако уровень 2 вызовет уровень 3, прежде чем он достигнет второго printf и, наконец, вернется.

Это будет продолжаться для всех уровней, пока мы не достигнем уровня 4. На уровне 4 оператор if оценивается false как , so up_and_down(n 1) никогда не достигается, и, таким образом, уровень 5 никогда не будет иметь значения.

Следовательно, уровень 4 является первым уровнем, который достигает своего неявного return значения . Уровень 4 задержал уровень 3, поэтому, когда уровень 4 устранен, уровень 3 может продолжить выполнение, и следующая инструкция в строке — printf("LEVEL %d......<something>", n, amp;n); where n = 3 . После этого уровень 3 достигает своего return и разблокирует уровень 2 и так далее.

Рекурсия работает как стек, а не как очередь.

 void up_and_down(int n)
{
    printf("Level %d: n location %pn", n, amp;n); // 1
    if (n < 4)
       up_and_down(n 1);
    printf("LEVEL %d: n location %pn", n, amp;n); // 2
    return;  // Return and unblock the function level that invoked this level, which is level n - 1
} 
 

Если вы все еще не понимаете рекурсию, прочитайте это еще раз.