Bevezetés a rekurzív funkcióba C
Az elemek hasonló módon történő ismétlésének a folyamatát, mint korábban, rekurziónak nevezzük. Azt mondják, hogy egy funkció rekurzív, ha önmagában hívják meg. A rekurziót a C programozási nyelv támogatja. Az alábbiakban két olyan feltétel van, amelyek kritikusak a C rekurzió megvalósításához:
- Kilépési feltétel: Ez a feltétel segíti a funkciót annak meghatározásában, hogy mikor lépjen ki a funkcióból. Ha nem adjuk meg a kilépési feltételt, akkor a kód végtelen hurokba lép.
- A számláló megváltoztatása : A számláló megváltoztatása az adott funkció minden hívásakor.
Ilyen módon rekurzív funkciót valósíthatunk meg a C programozási nyelven. Ezek a funkciók hasznosak olyan matematikai problémák megoldásában, amelyek megkövetelik egy hasonló folyamat többszörös meghívását. Ilyen problémák például a számos Fibonacci sorozat generációjának faktorszámának kiszámítása.
Szintaxis:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Hogyan működik a rekurzív funkció C-ben?
A rekurzív függvények képesek az egyenlet megvalósítására C programozási nyelven. Egy rekurzív függvényt hívunk fel egy argumentummal, amely átadódik n: n, a veremben lévő memóriát a helyi változóknak és a függvényeknek is hozzárendeljük. A funkcióban levő összes műveletet a memória segítségével hajtjuk végre. A kilépés feltételeit ellenőrzik, ha teljesül-e. Amikor a fordító más funkcióra hívást észlel, azonnal új memóriát oszt fel a verem tetején, ahol ugyanazok a helyi változók és a függvény másolatát készítik. Írja be ugyanazt a folyamatot folytatja.
Amikor az alapfeltétel visszatér igaznak, az adott érték továbbadódik a hívó funkcióhoz. A funkcióhoz hozzárendelt memória megszűnik. hasonlóképpen, az új értéket kiszámítják a hívó funkcióban, és az IT visszatér a szuper hívó funkcióba. Ilyen módon a funkció törlése rekurzív hívásokkal érkezik az első funkcióhoz, a teljes veremmemória törlődik, és a kimenet visszatér. Az alapfeltétel vagy a kilépési feltétel nem szerepel a függvényben, akkor a funkcióhoz való rekurzív hívások végtelen hurkot eredményezhetnek.
Példa a rekurzív funkcióra
Most meg fogjuk nézni a rekurzív funkció példáit a C-ben
Kód:
#include
int fun(int n)
(
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as it's argument .
//The value returned is multiplied with the argument passed in calling function.
)
int main()(
int test=4;
int result =0;
result =fun(test);
printf("%d", result);//prints the output result.
)
Kimenet:
A fenti kód magyarázata
A fenti példa egy szám tényezőjének megtalálása. Amikor a fő funkció fun (4) -et hív, akkor először ellenőrzi a kilépési feltételt (4 == 1), majd a 4 * fun (3) -ot hívja meg. Az alapfeltétel (3 == 1) ismét ellenőrzésre kerül. Hasonlóképpen, visszaadja a 3 * fun (2) hívást, és ez folytatódik akár 2 * fun (1) hívásig, és ahol megfelel az alapfeltételnek, és 1-et ad vissza, akkor a hívás funkció visszatér 2 * 1, majd, 3 * 2 * 1 és az első hívástól a 4 * 3 * 2 * 1 visszatér. Így a fő funkció tárolja a 24-et és kinyomtatja azt a kimeneten.
A rekurzív funkció memóriaelosztása
Minden c-nyelvű funkcióhívás memóriaelosztást eredményez a verem tetején. Amikor egy rekurzív funkciót memóriának hívnak, akkor az a memória tetején kerül hozzárendelésre, amelyet hozzárendeltek a hívó funkcióhoz, a funkció minden hívásakor a helyi változók különféle másolatai kerülnek létrehozásra.
Milyen alapfeltétel teljesül, a funkcióhoz rendelt memória elpusztul, és a mutató visszatér a hívó funkcióhoz? ezt a folyamatot megismételjük, majd az első hívási funkciót, és végre a veremmemória kiürül.
A fenti példában az alábbi szám tényezőjének kiszámításához a memória allokáció forgatókönyve van.
1. lépés
2. lépés
- 3. lépés
- 4. lépés
Lépés - 5
6. lépés
- 7. lépés
8. lépés
9. lépés
A rekurzió típusai
A C programozásban kétféle rekurzió létezik:
1. Farok és nem farkú rekurzió
A rekurzió fent megadott típusát az alábbiakban ismertetjük:
- Farok rekurzió
Ez egy olyan rekurzív függvény rekurzív hívás a függvényben, amely a függvény meghatározása során az utolsó művelet. A rekurzív hívás azt jelenti, hogy a funkció minden más logikája végrehajtásra kerül.
A farok-rekurzió használata a programunkban a hansis során a program teljesítményének csökkentése érdekében, és csökkenti az ilyen funkció memóriafelhasználását is. Ennek oka az, hogy mivel a funkció más logikája megvalósult a hívó funkcióhoz hozzárendelt memória számára, eltávolíthatók a veremből és felhasználhatók újra.
Kód:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Nem farkú rekurzió
Ez a rekurzív rekurzív kollázs a függvénydefiníció közepén készült. A férfi nadrág rekurziója befejeződött, és az értékek visszakerülnek a hívó funkcióhoz, még több lépést kell végrehajtani, így a memória nem törölhető.
Kód:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Közvetlen és közvetett rekurzió
A rekurzió fent megadott típusát az alábbiakban ismertetjük:
- Közvetett rekurzió
Azt mondják, hogy a közvetett rekurzió akkor fordul elő, amikor egy adott funkciót egy másik funkció rekurzív módon közvetítő közegének hívnak.
Kód:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Közvetlen rekurzió
Azt mondják, hogy a közvetlen rekurzió akkor fordul elő, amikor a funkció rekurzív hívása a saját meghatározása szerint történik. ”
Kód:
int fun1()(
fun1();
)
void main()(
fun1();
)
Következtetés
Könnyen megállapítható, hogy a rekurzív függvények legfontosabbak olyan matematikai feladatok megoldásában, amelyek megkövetelik egy hasonló módszer minden logikájának ismételt megvalósítását, amíg a kilépési feltétel teljesül. Sok probléma, például Hanoi tornyai, fa átjárások, a grafikonok mélységének kiszámítása.
Fontos megemlíteni a rekurzív funkció alapfeltételét. A memória és az időigény a rekurzív programoknál nagyobb, mint az iteratív programoknál, ezért ezeket óvatosan kell használni.
Ajánlott cikkek
Ez egy útmutató a C rekurzív funkció példájához. Itt tárgyaljuk a C rekurzív funkció működését, típusait, memóriaelosztását és példáit. A következő cikkeket megnézheti további információkért is -
- Tömbök a C programozásban
- Palindrome a C programban
- Minta a C programozásban
- C vs C ++
- Palindrome a JavaScript-ben
- Útmutató a Fibonacci sorozathoz JavaScript-en