Page 89 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Ці дві частини формують базову частину рекурсії. Інші
значення обчислюються за допомогою рекурсивної частини
рівняння:
F F F + F F + F F F
For n = 2, 2 = n = n 1– n 2– = 2   – 1 2   – 2 = 1 + 0
= 1 + 0 = 1.
F F F + F F + F F F
For n = 3, 3 = n = n 1– n 2– = 3   – 1 3   – 2 = 2 + 1 = 1 +
1 = 2.
F F F + F F + F F F
For n = 4, 4 = n = n 1– n 2– = 4   – 1 4   – 2 = 3 + 2 = 2 +
1 = 3.
F F F + F F + F F F
For n = 5, 5 = n = n 1– n 2– = 5   – 1 5   – 2 = 4 + 3 = 3 +
2 = 5.
F F F + F F + F F F
For n = 6, 6 = n = n 1– n 2– = 6   – 1 6   – 2 = 5 + 4 = 5 +
3 = 8.
F F F + F F + F F F
For n = 7, 7 = n = n 1– n 2– = 7   – 1 7   – 2 = 6 + 5 = 8 +
5 = 13.

Реалізація рекурсії для чисел Фібоначчі .

public static int fib(int n) {
if (n < 2) {
return n; // базисна частина
}
return fib(n-1) + fib(n-2); // рекурсивна частина
}
}
}

87