Рекурсия с ветвлением

 

До сих пор мы рассматривали примеры рекурсивных методов, в которых каждый экземпляр метода делал не более одного рекурсивного вызова. Однако вызовов может быть и больше. Рекурсия, при которой метод может вызвать себя несколько раз, называется ветвящейся (или рекурсией с ветвлением). Примером ветвящейся рекурсии является рекурсивный метод вычисления чисел Фибоначчи. Рассмотрим его подробнее.

Задача 6.2 Напишите рекурсивный метод, который вычисляет n-ый член последовательности чисел Фибоначчи.

Объяснение: математически последовательность Фибоначчи можно определить, как:

В методе будет два условия завершения рекурсии: при и и два рекурсивных вызова и .

import java.util.Scanner;public class FibR { static long fib(int n) { return (n>1)?fib(n-1)+fib(n-2):(n==1)?1:0; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); System.out.printf("Введите n:"); int n = scan.nextInt(); System.out.printf("fib(%d)= %d",n,fib(n)); } }

Результат:

Введите n:5

fib(5)= 5

Обратите внимание, что при вычислении fib(5) в соответствии с этой программой понадобится найти fib(4) и fib(3). Определение fib(4), в свою очередь, потребует вычисления fib(3) и fib(2), и так далее. Дерево вызовов метода fib(5) приведено на рис.6.3. Внимательно изучение содержимого стека вызовов для этой задачи показывает, что для нахождения каждого следующего числа Фибоначчи требуется примерно вдвое большее время, чем для определения предыдущего. Поэтому для практического применения такая программа не пригодна.