Как возвращаются значения при достижении базового варианта - PullRequest
Новая
       46

Как возвращаются значения при достижении базового варианта

1 голос
/ 06 июля 2019

Я изучал некоторые базовые алгоритмы, затем наткнулся на Евклидов алгоритм, чтобы найти GCD из двух чисел.

Я понял этот алгоритм на бумаге.Существует итеративный код, который делает то же самое. 

int euclid_gcd(int a, int b){
    int dividend = a>=b ? a : b;
    int divisor = a<=b ? a : b;
    while(divisor!=0){
        int remainder = dividend % divisor;
        dividend = divisor;
        divisor = remainder;
        }
    return dividend; 
}

Мне очень комфортно с приведенным выше итеративным кодом. Потом было еще две рекурсивные версии того же кода 

int gcd(int a, int b){
    if(a==b) 
        return a;
    if(a>b) 
        return gcd(a-b,b);
    return gcd(a,b-a);
}

И этонаименьший с точки зрения линий] 

int gcd(int a, int b){ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a);
}

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

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

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

Это моя попытка сухого запуска вышеуказанного кода (третий).Вызов функции: 

gcd(20,8);

gcd (20,8) -> gcd (8,20) -> gcd (4,8) -> gcd (0,4)

сейчасмы попали в базовый случай с помощью вызова функции gcd(0,4)

Он вернул 4

Теперь, как предыдущий вызов функции gcd(4,8) использовал это 4

Мы не «перехватываем» возвращаемое значение в какой-либо переменной. Тогда что именно происходит с этим значением и как окончательный ответ (в данном случае 4) всплывает и возвращается исходным вызовом функции?

Ответы [ 2 ]

2 голосов
/ 06 июля 2019

Я думаю, что ваше понимание рекурсии правильное и полное.Вам просто нужно немного узнать о роли Call Stack в вызовах функций.Вы можете найти много сообщений в Интернете, чтобы понять концепцию.Здесь я постараюсь дать вам краткое определение концепции Call Stack .

Память программы разделена на несколько сегментов.Двумя наиболее важными из них являются Stack и Heap .Здесь мы сосредоточимся на Stack .

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

Стек представляет собой структуру данных LIFO (Last-In-First-Out).Вы можете рассматривать его как коробку с идеально подобранными книгами - последняя, ​​которую вы положите, - первая, которую вы достаете.Используя эту структуру, программа может легко управлять всеми своими операциями и областями, используя две простые операции: push и pop.

enter image description here

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

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

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

2 голосов
/ 06 июля 2019

Рассмотрим этот пример: 

int functionA() {
    return functionB();
}

Этот код будет вызывать functionB и напрямую возвращать результат functionB вызывающей стороне functionA, не манипулируя им. Это эквивалентно написанию: 

int functionA() {
    int toReturn = functionB();
    return toReturn;
}

Как вы понимаете, значение, возвращаемое функцией B, "не перехвачено" явно определенной переменной в functionA.

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

...