Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Rekurzió

44
Valaki elmagyarázná mit ír ki f(3)-ra? Magát a menetét, a lépéseket
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Középiskola / Informatika

Válaszok

1
Mivel rekurzív függvényről van szó, célszerű megnézni, hogy sorban mi történik `x` különböző értékein.
`x=0`
Itt a függvény kiír egy 0-t, de ezzel vége is futásnak, mivel a while ciklus feltétele nem teljesül.
kimenet: 0

`x=1`
Itt már egy fokkal érdekesebb a helyzet. A függvény először kiír egy "1"-est, majd belép a while ciklusba. Itt meghívja az `f(0)`-t, ami (ahogy előbb láttuk) kiír egy "0"-t. Ezzel a program ismét befejeződik, mert `x`-nek `0` lesz az értéke.
kimenet: 10

`x=2`
A függvény kiírja a 2-t, majd meghívja az `f(1)-et`, ami kiírja az "10"-t, ahgoy ezt fentebb láttuk. Majd csökken 1-el `x` értéke, viszont ekkor már nem szakad meg a program, hanem újra a while elejére kerülünk. Most kiírja az "0"-t, és ismét vége a programnak.
kimenet: 2100

`x=3`
Elértünk a kérdés tárgyához. Először a függvény kiírja a "3"-at, majd meghívja az `f(2)` függvényt. Ez kiírja az előbb látott "2100" sorozatot. Ezután csökken `x` értéke `1`-el, és meghívódik az `f(1)` függvény, ami kiírja az "10" sorozatot. Végül ismét `f(0)`-val zárunk, ami "0"-t ír.
kimenet: 32100100

Ebből az is megfigyelhető hogy `f(n)` kimenete általánosan
`n + f(n-1) + f(n-2) + ... + f(0)`
(ahol az összeadás a kimenetek összefűzését próbálja szimbolizálni)

Lehet, valami olyan levezetésre gondoltál, hogy
`f(3)`
`\quad`kiírnunk `3`-at
`\qquad`belépünk az `f(2)` függvénybe
`\qquad\qquad`kiírunk 2-t
`\qquad\qquad`belépünk az `f(1)` függvénybe
`...`
`\qquad`belépünk az `f(1)` függvéybe
`...`
Szerintem rekurzív függvényen kicsit félrevezető így gondolkodni, mivel valóban lineárisan fut le, sokszor ez a lineáris felírás elrejti azt, hogy valójában mit csinál a függvény. Nyilván előfordulhat olyan is, hogy pont ez a felírás szükséges ahhoz, hogy gyorsan értelmezni tudjuk a függvényt, de úgy gondolom, hogy ez a ritkább eset. Végső soron ez a függvény azt csinálja, hogy kiírja a bemenetet, majd onnantól kezdve az összes alapcsonyabb bemenetű függvény kimenetét. Ezt a lineáris felírás olvashatatlanná teszi.
1