Ako riešiť rekurzia

Rekurzia je silný koncept v oblasti počítačovej vedy , ale to môže byť ťažké pre začiatočníkov pochopiť . Rekurzia zahŕňa funkciu alebo metódu opakovane odvoláva sa v inom kontexte , pokiaľ nie je dosiahnutá " základné " kontext a vrátil sa . Inými slovami , ako vyriešiť nejaký problém , program recontexualizes to ako trochu iný problém . Pri vykonávaní rekurzívny algoritmus , vždy zvážiť najjednoduchšie formu problému a vytvoriť tento zjednodušený príklad ako " základný prípad " , ktorý všetky ostatné verzie tohto problému bude odkazovať . Pokyny dovolená 1

Definujte hlavičku funkcie , je - meno funkcie a jeho vstupy . Napríklad , funkcia , ktorá nájde určitý počet Fibonacci by mohla vyzerať takto :

fib ( int n) { }

, funkcia spočíta " n - tý " Fibonacci číslo v poradí .
2

Napíšte , ako sa bude funkcia volaná všeobecne . Napríklad , keď zavoláte fib ( ) , budete používať jedno celé číslo ako argument a zaznamenajte číslo , že to spočíta :

int result = fib ( x ) ;
3

Definujte " základný prípad " vo vašom rekurzia problému . Tam môže byť viac základné prípady . Vzhľadom k tomu , Fibonacci sekvencie vyžaduje dve čísla , budete potrebovať dva základné prípady implementovať svoje riešenie

if (n == 0 ) return 0 ; . If (n == 1 ) return 1 ;

4

Definujte rekurzívne krok vášho rekurzia problém ako menšie , jednoduchšiu verziu toho istého problému , odkazom na príklad vyvolanie z kroku 2. V našom príklade Fibonacciho postupnosť je matematický sekvencia , kde každé číslo v rade je súčtom predchádzajúcich dvoch čísel v poradí . Algoritmus nájsť určitý počet Fibonacci teda musí dovolávať sa dvakrát , raz za predchádzajúce číslo a raz za číslo pred predchádzajúce číslo :

int result1 = fib (n - 1 ) ; int result2 = fib ( n - 2 ) ;

vrátiť result1 + result2 ;
5

Dajte funkcie dohromady , napr :

fib ( int n) { if (n == 0 ) return 0 ; //base case 1else if (n == 1 ) return 1 ; //base case 2

else { //rekurzívne stepint result1 = fib (n - 1 ) ; int result2 = fib (n - 2 ) ;

vrátiť result1 + result2 ; }

}

štruktúra " základné prípad " a " rekurzívne krok " budú rovnaké pre všetky rekurzívne funkcie , aj keď tam môže byť viac základné prípady a dlhé rekurzívne kroky .

• Predchádzajúca strana: Ako sa prihlásiť Konvolúcie v prostredí MATLAB bez použitia funkcie 
• Ďalšia strana: O SQL Profiler využitie