A Fibonacci szekvencia definíció szerint az az egész szekvencia, amelyben az első kettő után minden szám a két előző szám összege. Egyszerűsíteni:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…
Számos alkalmazása van a matematikában és még a kereskedelemben is (igen, ezt jól olvasta: kereskedés), de ez a cikk nem erről szól. A mai célom az, hogy megmutassam, hogyan lehet kiszámolni ennek a számsornak bármely tagját öt különböző programozási nyelven rekurzív függvények segítségével.
A rekurzív függvények azok a függvények, amelyek alapvetően önmagukat hívják.
Szeretném megjegyezni, hogy ez nem a legjobb módszer erre - valójában ezt a célt tekinthetjük a legalapvetőbb módszernek. Ennek oka, hogy a sorozat nagyobb feltételeinek kiszámításához szükséges számítási teljesítmény óriási. A függvényhívások száma a legtöbb nyelvben verem túlcsordulást okoz.
Mindazonáltal, az oktatóanyag céljából kezdjük.
Először is gondoljuk át, hogy fog kinézni a kód. A következőket tartalmazza:
· F rekurzív függvény (F a Fibonacci esetében): a következõ tag értékének kiszámításához.
· Semmi más: figyelmeztettelek, hogy elég alapos.
Funkciónk n- t vesz be bemenetként, amely a szekvencia n- edik kifejezésére utal, amelyet ki akarunk számítani. Tehát F (4) -nek vissza kell adnia a szekvencia negyedik tagját.
Tervezzük meg. A kódnak, nyelvtől függetlenül, ilyennek kell kinéznie:
function F(n) if n = 0
return 0 if n = 1
return 1 else
return F(n-1) + F(n-2)
Megjegyzés: a szekvencia 0 kifejezését 0-nak tekintjük, tehát az első tag 1 lesz; a második, 1; a harmadik, 2; stb. Érted.
Elemezzük egy pillanatra a függvényt. Ha 0-t kap bemenetként, akkor 0-t ad vissza. Ha 1-et kap, akkor 1-et ad vissza. Ha 2-t kap ... Nos, ebben az esetben az else utasításba esik, amely a 2–1 ( 1) és 2–2 (0). Ez 1-t és 0-t ad vissza, és a két eredmény hozzáadódik, így az 1. Tökéletes.
Most láthatja, hogy a rekurzív függvények miért jelentenek problémát bizonyos esetekben. Képzelje el, hogy a sorozat 100. tagját szeretné. A függvény a 99-es és a 98-asra hívná magát, amely maga is a 98-as és 97-es, valamint 97-es és 96-os kifejezésre hívná a funkciót ... Nagyon lassú lenne .
De a jó hír az, hogy valóban működik!
Kezdjük tehát a különböző nyelvekkel. Nem adok túl sok részletet (valójában egyáltalán nem), hogy jobbá tegyem olvasási élményét. Egyébként nincs túl sok részlet.
Ugorjunk bele:
Piton
def F(n): if n == 0:
return 0 if n == 1:
return 1 else:
return F(n-1) + F(n-2)
Gyors
func F(_ n: Int) -> Int { if n == 0 { return 0
} if n == 1 { return 1
} else { return F(n-1) + F(n-2)
}}
JavaScript
function F(n) { if(n == 0) { return 0;
} if(n == 1) { return 1;
} else { return F(n-1) + F(n-2);
}}
Jáva
public static int F(int n) { if(n == 0) { return 0;
} if(n == 1) { return 1;
} else { return F(n-1) + F(n-2);
}}
C ++
int F(int n) { if(n == 0) { return 0;
} if(n == 1) { return 1;
} else { return F(n-1) + F(n-2);
}}
És ez az. Ezeket a nyelveket csak a népszerűség alapján választottam - vagy legalábbis azért, mert ez az 5 a leggyakoribb, amelyet használok. Nincsenek külön sorrendben. A szintaxis nehézségei szerint véleményem szerint a Python-tól (a legkönnyebb) a C ++ -ig (a legnehezebb). De ez a személyes véleményétől és az egyes nyelvekkel kapcsolatos tapasztalataitól függ.
Remélem, tetszett ez a cikk, és ha bármilyen kérdése / javaslata van, vagy csak köszönni szeretne, kommentálja alább!