Gyakorlati alapok II.
Rekurzió
Fibonacci-sorozat
Az Egy középkori zseni: Signore Fibonacci című fejezetben ismertettük ezen nagyon híres számsorozat matematikai és kódalapjait. Nézzük meg rekurzív megoldását is:
public class Main {
public static int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n
- 2);
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Végeredmény:
55
A kód gyenge pontja a kiírás, mert csak egyetlen számot mutat (a sorozat 11. eleme), tehát nem ad Fibonacci-sorozatot:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181...
Ennek eléréséhez kissé módosítsuk a kódot:
public class Main {
public static int fibonacci(int i){
if (i == 0) return 0;
if (i == 1) return 1;
return fibonacci(i - 1) + fibonacci(i - 2);
}
public static void main(String[] args){
int i = 0;
do{
System.out.print(fibonacci(i) + " ");
i++;
}while(i <= 10);
}
}
Végeredmény:
0 1 1 2 3 5 8 13 21 34 55
A kód érdekessége, hogy a sorozat futásának számhatárát egy egészen eldugott helyen, a hátultesztelő do-while ciklus feltételében kell beállítani.
Házi feladat - Módosítsuk a kódot, hogy a számhatár megadását egyszerű adatbekéréssel oldjuk meg!
A megoldás fejezete a képre kattintva érhető el.
Pénzes László