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

Ответ 1

Предположим, что функция:

int MyFunc(int counter) {
    // check this functions counter value from the stack (most recent push)

    // if counter is 0, we've reached the terminating condition, return it
    if(counter == 0) {
        return counter;
    }
    else {
        // terminating condition not reached, push (counter-1) onto stack and recurse
        int valueToPrint = MyFunc(counter - 1);

        // print out the value returned by the recursive call 
        printf("%d", valueToPrint);

        // return the value that was supplied to use 
        // (usually done via a register I think)
        return counter;
    }
}

int main() {
    // Push 9 onto the stack, we don't care about the return value...
    MyFunc(9);
}

Выход: 0123456789

В первый раз через MyFunc число равно 9. Оно терпит неудачу с завершающей проверкой (это не 0), поэтому вызывается рекурсивный вызов, с (счетчик -1), 8.

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

Следующий вызов стека использует возвращаемое значение для печати (0), а затем возвращает значение, которое было отправлено в него при его вызове (1). Это повторяется:

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

Итак, если MyFunc был вызван с 3, вы получите эквивалент (игнорируя обратные адреса и т.д. из стека):

Call MyFunc(3) Stack: [3]
Call MyFunc(2) Stack: [2,3]
Call MyFunc(1) Stack: [1,2,3]
Call MyFunc(0) Stack: [0,1,2,3]
Termination fires (top of stack == 0), return top of stack(0).
// Flow returns to:
MyFunc(1) Stack: [1,2,3]
Print returned value (0)
return current top of stack (1)

// Flow returns to:
MyFunc(2) Stack: [2,3]
Print returned value (1)
return current top of stack (2)

// Flow returns to:
MyFunc(3) Stack: [3]
Print returned value (2)
return current top of stack (3)

// and you're done...

Ответ 2

В C рекурсия похожа на обычные вызовы функций.

• Когда вызывается функция, аргументы, обратный адрес и указатель кадра (я забыл порядок) помещаются в стек.
• В вызываемой функции сначала пространство для локальных переменных "толкается" в стек.
• Если функция возвращает что-то, поместите ее в определенный регистр (зависит от архитектуры, AFAIK)
• отменить шаг 2.
• отменить шаг 1.

Итак, с этапами рекурсии 1 и 2 выполняются несколько раз, тогда возможно 3 (возможно, только один раз) и, наконец, 4 и 5 (столько раз, сколько 1 и 2).

Ответ 3

Как все происходит, когда достигнуто условие выхода?

Во-первых, несколько слов о рекурсии: метод разделения и захвата, используемый для сложных задач, которые можно постепенно разложить и свести к простым примерам первоначальной задачи до тех пор, пока форма ^{(базовый регистр)} не позволит получить прямой расчет. Это понятие тесно связано с математической индукцией .

Более конкретно, рекурсивная функция вызывает себя, прямо или косвенно. В функции прямой рекурсии foo() делает другой вызов самому себе. В косвенной рекурсии функция foo() выполняет вызов функции moo(), которая, в свою очередь, вызывает функцию foo(), пока не будет достигнут базовый случай, а затем окончательный результат аккумулируется в точном обратном порядке исходной рекурсивной вызов функции.

Пример:

Факториал n, обозначенный n!, является произведением положительных целых чисел от 1 до n. Факториал может быть формально определен как:
factorial (0) = 1, (базовый случай)
factorial (n) = n * factorial (n-1), при n > 0. ( рекурсивный вызов)

Рекурсия появляется в этом определении, поскольку мы определяем факториал (n) в терминах factorial (n-1).

Каждая функция рекурсии должна иметь условие завершения, чтобы завершить рекурсию. В этом примере, когда n = 0, рекурсия прекращается. Вышеуказанная функция, выраженная в C, такова:

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

Этот пример является примером прямой рекурсии.

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

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

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

Также может ли кто-нибудь дать мне схематический вид рекурсии?

На следующем рисунке показана запись активации для факториала (3):

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

Ответ 4

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