Как результаты возврата вычисляются в рекурсивной функции?

Question

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

Предположим, у меня есть функция для подсчета, что сколько раз символ появляется в строке.

int frequency(char ch, string input, int pos) { 
    if (pos == inputString.length()) { 
     return 0; 
    } 

    if (inputString[pos] == ch) { 
     return 1 + frequency(ch, inputString, pos + 1); 
    } 
    else { 
     return frequency(ch, inputString, pos+1); 
    } 
} 

Если бы я пройти к ней, строка «Jeff» и ищет «е», то она возвращает значение 2.

Итак, как он узнает, когда остановиться?

• ли return 0 конец любой метод с возвращаемым типом int?

• И если да, то почему он до сих пор возвращает значение 2, когда окончательного возвращение говорит вернуться 0?

Answer 1

Последнее возвращение

return 0; 

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

return 1 + frequency(ch, inputString, pos + 1); 

Таким образом, 0 добавляется до и любых предыдущих результатов 1 из рекурсии.

PS: До тех пор, пока оператор return функции снова вызовет эту функцию, рекурсия продолжается. Только когда возвращение просто возвращает что-то (без повторного вызова fucntion), рекурсия прекращается.

Вот более простой пример, который вычисляет сумму всех целых чисел до N:

int calcSum(int N){ 

    if (N == 1) return 1;   // recursion stops here 

    return N + calcSum(N-1);  // otherwise continue to add up 

} 

несколько операторов возврата в одной функции не являются специальными рекурсии. Функция просто возвращается при первом возвращении, с которым она сталкивается.

Answer 2

Подумайте о рекурсивных вызовах как стек вызовов функций. В какой-то момент он может попасть в return 0; Это означает, что один из вызовов функций в стеке завершен. Таким образом, появляется элемент в стеке. Функция final возврат происходит, когда стек пуст.

Answer 3

Итак, как он узнает, когда остановиться?

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

if (pos == inputString.length()) { 
    return 0; 
} 

Любые из других ветвей вызвать функцию рекурсивен и сделать шаг вниз в стеке вызовов:

if (inputString[pos] == ch) { 
    return 1 + frequency(ch, inputString, pos + 1); 
      // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
} 
else { 
    return frequency(ch, inputString, pos+1); 
     // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
} 

• ли return 0; конца любого метода с обратным типом междунаром ?

Да, и он будет делать для любых типов возврата, которые могут быть инициализированы с 0

• И если да, то почему он до сих пор возвращает значение 2, когда окончательное возвращение говорит возвращение 0?

Поскольку результаты результатов рекурсивных вызовов были накоплены в стеке:

return 1 + frequency(ch, inputString, pos + 1); 
//  ^the result of the operation will be saved on the stack when the call returns 

... и вы видите конечный результат (первый) рекурсивного вызова в вашей функции драйвера.

---

BTW, гораздо более дешевая реализация с использованием производительности и использования памяти была бы простой петлей. В любом случае нет никаких ограничений относительно линейного поведения времени:

int frequency(char ch, string input) { 
    int result = 0; 
    for(int pos = 0; pos < input.size(); ++pos) { 
     if (input[pos] == ch) { 
      ++result; 
     } 
    } 
    return result; 
}