Почему этот тип рекурсии работает как возвращаемое значение?

Question

Мы используем значение n для выполнения рекурсии. Мы сохраняем это значение в переменной x. Затем переменная x добавляется в рекурсию в качестве возвращаемого значения. Как именно это работает?

Я попробовал разные подходы, чтобы проверить, используете ли вы сначала рекурсию для x, а затем x, чтобы добавить ее в другую рекурсию.

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

int up(int n)
{
    int x;

    if(n == 0)
    {
        return 0;
    }
    else if(n == 1)
    {
        return 1;
    }
    else
    {
        x = up(n - 2);
        return x + up(n - 1);
    }
}

int main(void)
{
     int n = 20;
     int res;
     res = up(n);
     printf("Result %d\n", res);
     return 0;
}

Результат 6765. Так как это код из школы, результат должен быть в порядке. Я просто не понимаю, почему.

Answer 1

Привязки аргументов уникальны для каждого вызова. Это означает, что n в up(20) никогда не смешивается с n в up(19). Поскольку это не ссылка, n - 1 вычисляется и передается как новое значение в другом месте, чем старое, поэтому при возврате старого n остается тем же, чем всегда во время дополнительных вызовов. Локальные переменные также существуют только в области видимости, и поэтому каждый x также отличается.

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

Базовые корпуса:

up(0) => 0
up(1) => 1

Случаи по умолчанию:

up(2) => up(2-2) + up(2-1) => up(0) + up(1) => 0 + 1 

Теперь я знал результаты 0 и 1 из базовых случаев там, и вы можете просто заменить их на результат. Мы можем пойти дальше:

up(3) => up(3-2) + up(3-1) => 1 + 1 => 2
up(4) => up(4-2) + up(4-1) => 1 + 2 => 3
up(5) => up(5-2) + up(5-1) => 2 + 3 => 5
...

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

Answer 2

Вот как можно упростить функцию:

int Fib(int n)
{
    return (n<2 ? n : Fib(n-1) + Fib(n-2));
}

Это просто C, а не C ++

Answer 3

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

Stack:

Допустим, n = 5 для упрощенного примера. Up (5) помещается в стек. Затем вы объявляете, что x внутри этой области видимости функции UP (3). Теперь UP (3) помещается в стек, а UP (5) ожидает возврата Up (3). Заказ стека: Up(3) Up(5)

Теперь Up (3) объявляет x внутри этой функции как UP (1) и терпеливо ждет возврата Up (1). Поскольку x объявлен внутри функции, они являются локальными переменными, доступными только внутри функции, которая их объявила. Это означает, что X внутри Up (3) хранится в совершенно другом месте в памяти, как X внутри Up (5). Вы определенно узнаете больше об этом, когда будете исследовать адресные пространства и то, как хранятся локальные переменные и тому подобное. Но продолжаем вперед!

Stack: Up(1) Up(3) Up(5) Up (1) возвращает 1, и поэтому мы выталкиваем его из стека! Это означает, что Up (3) может продолжить работу. Стек: Up(3) Up(5) Up (3) теперь имеет x = 1 (возврат Up (1) и желает вернуть x + Up (2). Для этого мы помещаем Up (2) в стек.

Stack: Up(2) Up(3) Up(5)

Продолжая этот пример, Up (2) добавит Up (0) в стек. Up (0) вернет 0, поэтому x внутри области видимости для Up (2) будет установлено в 0. Up (2) добавит Up (1) в стек, что вернет 1. Up (2) вернет (0 + 1). Теперь мы можем вернуться к Up (3), вытолкнув Up (2) из ​​стека. Up (3) имеет x = 1 и желает вернуться (1 + 1). Подняв вверх (3) со стека, мы остаемся с Up (5) в стеке. X теперь установлен в 2 из-за возврата Up (3). Теперь мы добавляем Up (4) в стек, который добавляет Up (2), Up (0), Up (1), Up (3), Up (2), Up (0), Up (1) в этом порядке Примечание (многие из этих вызовов отменяются до добавления новых).

Я рекомендую прочитать о глобальной области действия и области действия функции. Понимание этих концепций очень важно для основ понимания рекурсии. Однако вы уже можете видеть, что этот тип рекурсии довольно грубый и совсем не оптимизирован. Например, вы вычисляете Up (2) несколько раз для каждого созданного рекурсивного вызова. Это приводит к проблеме масштабируемости при работе с большими числами, поскольку вы повторяете одну и ту же операцию несколько раз для одного и того же номера. Эту проблему можно решить с помощью массива памятки и немного большей логики для меньшего времени выполнения Big O, но это может быть слишком подробно для этого вопроса.