Как работает рекурсия в C?

Question

Я пытаюсь понять, как работает рекурсия в C. Кто-нибудь может дать мне объяснение потока управления?

#include <stdio.h>
/* printd: print n in decimal */
void printd(int n)
{
  if (n < 0)
  {
    putchar('-');
    n = -n;
  }
  if (n / 10) printd(n / 10);
  putchar(n % 10 + '0');
}

int main()
{
  printd(123);
  return 0;
}

Answer 1

Поток управления выглядит следующим образом (где -> - это вызов функции)

main()
 └─> printd(123)
      ├─> printd(12)
      │    ├─> printd(1)
      │    │    └─> putchar('1')
      │    └─> putchar('2')
      └─> putchar('3')

Answer 2

Call printd(123)
    (123 / 10) != 0, so Call printd(12)
        (12 / 10) != 0, so Call printd(1)
            (1 / 10) == 0, so Call putchar "1"
        Call putchar "2"
    Call putchar "3"
return 0 (from main())

Answer 3

enter code here




main()
{print f ("stat");
main();
print f ("end")  ;
}

введите код здесь

main()
{int n, res;
pf("enter n value");
sf("%d",&n);

=fact(n);
}
int fact(int n)
{int res;
if(n==0)
{
res=1;
}
else
{
res = n*fact (n-1);
}
return res;
}

Answer 4

Чтобы понять рекурсию, вам нужно понять модель хранилища.Хотя есть несколько вариантов, в основном «автоматическое» хранение, хранилище, используемое для хранения автоматических переменных, параметров, температуры компилятора и информации о вызове / возврате, организовано как «стек».Это структура хранения, начинающаяся в некотором месте в хранилище процессов и «растущая» либо «вверх» (увеличение адресов), либо «вниз» (уменьшение адресов) при вызове процедур.

Можно начать с парыпеременных:

00 -- Variable A -- 27
01 -- Variable B -- 45

Затем мы решаем вызвать процедуру X, поэтому мы генерируем параметр A + B:

02 -- Parameter -- 72

Нам нужно сохранить местоположение, в котором мы хотим контролироватьвернуть.Скажем, инструкция 104 является вызовом, поэтому мы сделаем 105 обратным адресом:

03 -- Return address -- 105

Нам также нужно сохранить размер вышеупомянутого «стека фрейма» - четыре слова, 5 с размером фреймаСамо по себе:

04 -- Frame size -- 5

Теперь мы начинаем выполнение в X. Ему нужна переменная C:

05 -- Variable C -- 123

И она должна ссылаться на параметр.Но как это сделать?Ну, при входе указатель стека был установлен так, чтобы он указывал на «дно» «кадра стека» X.Мы могли бы сделать «низ» любым из нескольких мест, но давайте сделаем его первой переменной в кадре X.

05 -- Variable C -- 123  <=== (Stack frame pointer = 5)

Но нам все равно нужно ссылаться на параметр.Мы знаем, что «ниже» нашего фрейма (на который указывает указатель фрейма стека) находятся (в порядке убывания адреса) размер фрейма, адрес возврата, а затем наш параметр.Поэтому, если мы вычтем 3 (для этих 3 значений) из 5, мы получим 2, которое является местоположением параметра.

Обратите внимание, что на данный момент нам не важно, равен ли наш указатель кадра 5 или 55555- мы просто вычитаем ссылочные параметры, добавляем для ссылки наши локальные переменные.Если мы хотим сделать вызов, мы «складываем» параметры, адрес возврата и размер кадра, как мы это делали при первом вызове.Мы могли бы делать вызов после вызова после вызова и просто продолжать «проталкивать» стековые кадры.

Чтобы вернуть нас, загрузите размер кадра и адрес возврата в регистры.Вычтите размер кадра из указателя кадра стека и поместите адрес возврата в счетчик команд, и мы вернемся к процедуре вызова.

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

Answer 5

Рекурсия работает в стеке, т. Е. Первый в последнем выходе.

Рекурсия - это процесс вызова себя с другими параметрами, пока не будет достигнуто базовое условие. Переполнение стека происходит, когда выполняется слишком много рекурсивных вызовов.

Answer 6

#include <stdio.h>

#define putd(d) (printf("%d", d))

#define RECURSIVE

void rprint(int n)
{
#ifndef RECURSIVE
    int i = n < 0 ? -n : n;

    for (; i / 10; i /= 10)
        putd(i % 10);

    putd(i % 10);

    if (n < 0)
        putchar('-');
    /* Don't forget to reverse :D */
#else
    if (n < 0) {
         n = -n;
         putchar('-');
    }

    int i = n / 10;
    if (i)
        rprint(i);

    putd(n % 10);
#endif
}

int main()
{
    rprint(-321);
    return 0;
}

Answer 7

Вы имеете рекурсию в C (или любом другом языке программирования), разбив задачу на две меньшие задачи.

Ваш пример: печать числа может быть разбита на эти 2 части

1. распечатать первую часть, если она существует
2. напечатать последнюю цифру

Чтобы напечатать «123», проще всего напечатать «12» (12 is 123 / 10) и вывести «3».
Чтобы напечатать «12», проще всего напечатать «1» (1 is 12 / 10) и напечатать «2».
Для печати«1», ... просто выведите «1».