Рекурсия

Рекурсия — это вызов методом самого себя.

Рассмотрим вычисление произвольного числа ряда Фибоначчи. Первое число ряда Фибоначчи равно 0, второе — 1, i-е число равно сумме (i-1)-го и (i-2)-го чисел.

public static long fib(int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return fib(i-1) + fib(i-2);
}

Обратите внимание, вместо int здесь используется тип long, диапазон значений которого значительно больше.

Схематически вычисление пятого числа из ряда Фибоначчи можно представить так:

{"name":"fib 5","subCalls":[{"name":"fib 4","subCalls":[{"name":"fib 3","subCalls":[{"name":"fib 2","subCalls":[{"name":"fib 1","subCalls":[]},{"name":"fib 0","subCalls":[]}]},{"name":"fib 1","subCalls":[]}]},{"name":"fib 2","subCalls":[{"name":"fib 1","subCalls":[]},{"name":"fib 0","subCalls":[]}]}]},{"name":"fib 3","subCalls":[{"name":"fib 2","subCalls":[{"name":"fib 1","subCalls":[]},{"name":"fib 0","subCalls":[]}]},{"name":"fib 1","subCalls":[]}]}]}
Комментарии к уроку

Сообщить об ошибке