Нужно предугадать результат рекурсии. Java

Question

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

static int rec(int a) {
    if (a == 40)
        return a;
    else
        return (a + rec(a*2));
}
public static void main(String[] args) {
    System.out.println(rec(5));
}

Answer 1

Начинаем отсюда:

main(){
 System.out.println(rec(5));
}

Теперь рассмотрим функцию. Переменная a, переданная в функцию = 5.

int rec(int a)

Рассмотрим условие:

 if (a == 40)
 return a;

Так как a = 5, то условие ложно, следовательно переходим в секцию else.

return (a + rec(a*2);

Как видно, мы возвращаем 5 + rec(5 * 2). Заметим, что так как функция выполняется рекурсивно, то итоговый результат не будет получен, пока рекурсивные вызовы rec() не будут обработаны и посчитаны полностью. Иными словами, рекурсивные вызовы закончатся тогда, когда входной параметр a будет равен 40.

Трассировка будет выглядеть примерно так:

5 + rec(5 * 2) => 5 + 10 + rec(10 * 2) => 5 + 10 + 20 + rec(20 * 2) => 5 + 10 + 20 + 40 = 75

P.S. Надеюсь не ошибся в вычислениях xD

Answer 2

Предположим, что рекурсия всё-таки завершается.
Тогда последний вызов: rec(40) = 40
Вызов с аргументом 40 может быть только прямым или из rec(20), который вернёт 20+rec(40)

Итак,

rec(40) = 40
rec(20) = 20 + 40 = 60
rec(10) = 10 + 60 = 70
rec(5)  =  5 + 70 = 75

_{Нетрудно понять, что для любых других целых аргументов рекурсия не завершится.}

БЛОГ НА HUSL

Нужно предугадать результат рекурсии. Java

Ответы (2 шт):