Rekursion er et grundlæggende koncept inden for datalogi og matematik, der tillader funktioner at kalde sig selv, hvilket muliggør løsning af komplekse problemer gennem iterative trin. En visuel repræsentation, der almindeligvis bruges til at forstå og analysere udførelsen af ​​rekursive funktioner, er et rekursionstræ. I denne artikel vil vi udforske teorien bag rekursionstræer, deres struktur og deres betydning for forståelsen af ​​rekursive algoritmer.

Hvad er et rekursionstræ?

Et rekursionstræ er en grafisk repræsentation, der illustrerer udførelsen af ​​en rekursiv funktion. Det giver en visuel opdeling af rekursive opkald, der viser algoritmens progression, efterhånden som den forgrener sig og i sidste ende når en basiscase. Træstrukturen hjælper med at analysere tidskompleksiteten og forstå den involverede rekursive proces.

Træstruktur

Hver knude i et rekursionstræ repræsenterer et bestemt rekursivt kald. Det første opkald er afbildet øverst, med efterfølgende opkald, der forgrener sig under det. Træet vokser nedad og danner en hierarkisk struktur. Forgreningsfaktoren for hver knude afhænger af antallet af rekursive opkald foretaget i funktionen. Derudover svarer træets dybde til antallet af rekursive opkald, før det når basissagen.

Bundkasse

Basistilfældet fungerer som termineringsbetingelsen for en rekursiv funktion. Den definerer det punkt, hvor rekursionen stopper, og funktionen begynder at returnere værdier. I et rekursionstræ er noderne, der repræsenterer basistilfældet, normalt afbildet som bladknuder, da de ikke resulterer i yderligere rekursive kald.

Rekursive opkald

De underordnede noder i et rekursionstræ repræsenterer de rekursive kald, der foretages i funktionen. Hver underordnet node svarer til et separat rekursivt kald, hvilket resulterer i oprettelsen af ​​nye underproblemer. Værdierne eller parametrene, der sendes til disse rekursive kald, kan variere, hvilket fører til variationer i underproblemernes karakteristika.

Udførelsesflow:

At krydse et rekursionstræ giver indsigt i udførelsen af ​​en rekursiv funktion. Startende fra det indledende opkald ved rodknudepunktet, følger vi grenene for at nå efterfølgende opkald, indtil vi støder på basissagen. Efterhånden som basistilfældene nås, begynder de rekursive kald at vende tilbage, og deres respektive noder i træet er markeret med de returnerede værdier. Traverseringen fortsætter, indtil hele træet er gennemkørt.

Tidskompleksitetsanalyse

Rekursionstræer hjælper med at analysere tidskompleksiteten af ​​rekursive algoritmer. Ved at undersøge træets struktur kan vi bestemme antallet af rekursive opkald, der er foretaget, og det udførte arbejde på hvert niveau. Denne analyse hjælper med at forstå den overordnede effektivitet af algoritmen og identificere eventuelle potentielle ineffektiviteter eller muligheder for optimering.

Introduktion

• Tænk på et program, der bestemmer et tals faktor. Denne funktion tager et tal N som input og returnerer fakultetet af N som et resultat. Denne funktions pseudo-kode vil ligne,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Rekursion er eksemplificeret ved den funktion, der tidligere blev nævnt. Vi påberåber os en funktion til at bestemme et tals faktor. Så, givet en mindre værdi af det samme tal, kalder denne funktion sig selv. Dette fortsætter, indtil vi når det grundlæggende tilfælde, hvor der ikke er flere funktionskald.
• Rekursion er en teknik til at håndtere komplicerede problemstillinger, når resultatet er afhængigt af udfaldene af mindre tilfælde af samme problem.
• Hvis vi tænker på funktioner, siges en funktion at være rekursiv, hvis den bliver ved med at kalde sig selv, indtil den når basissagen.
• Enhver rekursiv funktion har to primære komponenter: basistilfældet og det rekursive trin. Vi holder op med at gå til den rekursive fase, når vi når den grundlæggende sag. For at forhindre endeløs rekursion skal basecases være korrekt defineret og er afgørende. Definitionen af ​​uendelig rekursion er en rekursion, der aldrig når basistilfældet. Hvis et program aldrig når basistilfældet, vil stakoverløb fortsætte med at forekomme.

Rekursionstyper

Generelt er der to forskellige former for rekursion:

• Lineær rekursion
• Træ rekursion
• Lineær rekursion

Lineær rekursion

• En funktion, der kalder sig selv én gang, hver gang den udføres, siges at være lineært rekursiv. En god illustration af lineær rekursion er den faktorielle funktion. Navnet 'lineær rekursion' henviser til det faktum, at en lineær rekursiv funktion tager en lineær mængde tid at udføre.
• Tag et kig på pseudokoden nedenfor:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Hvis vi ser på funktionen doSomething(n), accepterer den en parameter ved navn n og udfører nogle beregninger, før den kalder den samme procedure igen, men med lavere værdier.
• Når metoden doSomething() kaldes med argumentværdien n, lad os sige, at T(n) repræsenterer den samlede tid, der er nødvendig for at fuldføre beregningen. Til dette kan vi også formulere en gentagelsesrelation, T(n) = T(n-1) + K. K fungerer som en konstant her. Konstant K er inkluderet, fordi det tager tid for funktionen at allokere eller deallokere hukommelse til en variabel eller udføre en matematisk operation. Vi bruger K til at definere tiden, da den er så lille og ubetydelig.
• Dette rekursive programs tidskompleksitet kan ganske enkelt beregnes, da metoden doSomething() i værste tilfælde kaldes n gange. Formelt set er funktionens tidsmæssige kompleksitet O(N).

Træ rekursion

• Når du foretager et rekursivt opkald i dit rekursive tilfælde mere end én gang, omtales det som trærekursion. En effektiv illustration af trærekursion er fibonacci-sekvensen. Træets rekursive funktioner fungerer i eksponentiel tid; de er ikke lineære i deres tidsmæssige kompleksitet.
• Tag et kig på pseudokoden nedenfor,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Den eneste forskel mellem denne kode og den forrige er, at denne kalder endnu et kald til den samme funktion med en lavere værdi på n.
• Lad os sætte T(n) = T(n-1) + T(n-2) + k som gentagelsesrelationen for denne funktion. K fungerer som en konstant igen.
• Når mere end et kald til den samme funktion med mindre værdier udføres, er denne form for rekursion kendt som trærekursion. Det spændende aspekt er nu: Hvor tidskrævende er denne funktion?
• Tag et gæt baseret på rekursionstræet nedenfor for den samme funktion.
  
• Det kan gå op for dig, at det er udfordrende at estimere tidskompleksiteten ved at se direkte på en rekursiv funktion, især når det er en trærekursion. Recursion Tree Method er en af ​​flere teknikker til at beregne den tidsmæssige kompleksitet af sådanne funktioner. Lad os undersøge det mere detaljeret.

Hvad er rekursionstræmetoden?

• Gentagelsesrelationer som T(N) = T(N/2) + N eller de to, vi dækkede tidligere i afsnittet om typer af rekursion, løses ved hjælp af rekursionstræ-tilgangen. Disse tilbagevendende relationer bruger ofte en adskille og hersk-strategi til at løse problemer.
• Det tager tid at integrere svarene på de mindre underproblemer, der skabes, når et større problem opdeles i mindre underproblemer.
• Gentagelsesrelationen er for eksempel T(N) = 2 * T(N/2) + O(N) for flettesorteringen. Den tid, der er nødvendig for at kombinere svarene på to underproblemer med en kombineret størrelse på T(N/2) er O(N), hvilket også gælder på implementeringsniveau.
• For eksempel, da gentagelsesrelationen for binær søgning er T(N) = T(N/2) + 1, ved vi, at hver iteration af binær søgning resulterer i et søgerum, der er skåret i to. Når resultatet er bestemt, forlader vi funktionen. Gentagelsesrelationen er tilføjet +1, fordi dette er en konstant tidsoperation.
• Gentagelsesrelationen T(n) = 2T(n/2) + Kn er en at overveje. Kn angiver den tid, der kræves for at kombinere svarene på n/2-dimensionelle underproblemer.
• Lad os afbilde rekursionstræet for det førnævnte gentagelsesforhold.

Vi kan drage et par konklusioner fra at studere rekursionstræet ovenfor, herunder

1. Størrelsen af ​​problemet på hvert niveau er alt, der betyder noget for at bestemme værdien af ​​en node. Problemstørrelsen er n på niveau 0, n/2 på niveau 1, n/2 på niveau 2, og så videre.

2. Generelt definerer vi træets højde som lig med log (n), hvor n er størrelsen af ​​problemet, og højden af ​​dette rekursionstræ er lig med antallet af niveauer i træet. Dette er sandt, fordi, som vi lige har fastslået, opdel-og-hersk-strategien bruges af gentagelsesrelationer til at løse problemer, og at komme fra problemstørrelse n til problemstørrelse 1 kræver blot at tage log (n) trin.

• Overvej f.eks. værdien af ​​N = 16. Hvis vi får lov til at dividere N med 2 på hvert trin, hvor mange trin skal der så til for at få N = 1? I betragtning af at vi dividerer med to på hvert trin, er det rigtige svar 4, som er værdien af ​​log(16) base 2.

log(16) base 2

log(2^4) base 2

4 * log(2) base 2, da log(a) base a = 1

så 4 * log(2) base 2 = 4

3. På hvert niveau betragtes det andet led i gentagelsen som roden.

Selvom ordet 'træ' optræder i denne strategis navn, behøver du ikke at være ekspert i træer for at forstå det.

Hvordan man bruger et rekursionstræ til at løse gentagelsesrelationer?

Omkostningerne ved underproblemet i rekursionstræteknikken er mængden af ​​tid, der er nødvendig for at løse underproblemet. Derfor, hvis du bemærker udtrykket 'omkostning' forbundet med rekursionstræet, refererer det blot til mængden af ​​tid, der er nødvendig for at løse et bestemt underproblem.

Lad os forstå alle disse trin med et par eksempler.

Eksempel

Overvej gentagelsesforholdet,

java værdi af streng

T(n) = 2T(n/2) + K

Løsning

Den givne gentagelsesrelation viser følgende egenskaber,

En opgavestørrelse n er opdelt i to underopgaver hver af størrelse n/2. Omkostningerne ved at kombinere løsningerne på disse delproblemer er K.

Hver opgavestørrelse på n/2 er opdelt i to underopgaver hver på størrelse n/4 og så videre.

På sidste niveau vil delproblemstørrelsen blive reduceret til 1. Med andre ord rammer vi endelig basissagen.

Lad os følge trinene for at løse denne gentagelsesrelation,

Trin 1: Tegn rekursionstræet

Trin 2: Beregn træets højde

Da vi ved, at når vi kontinuerligt dividerer et tal med 2, kommer der et tidspunkt, hvor dette tal reduceres til 1. Det samme som med problemstørrelsen N, antag, at efter K dividerer med 2, bliver N lig med 1, hvilket indebærer, ( n / 2^k) = 1

Her er n / 2^k problemstørrelsen på det sidste niveau, og den er altid lig med 1.

Nu kan vi nemt beregne værdien af ​​k ud fra ovenstående udtryk ved at tage log() til begge sider. Nedenfor er en mere klar afledning,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) base 2

Så højden af ​​træet er log (n) base 2.

Trin 3: Beregn omkostningerne på hvert niveau

• Omkostninger på niveau-0 = K, to delopgaver er slået sammen.
• Omkostninger på niveau-1 = K + K = 2*K, to delopgaver slås sammen to gange.
• Omkostninger på niveau-2 = K + K + K + K = 4*K, to delopgaver slås sammen fire gange. og så videre....

Trin 4: Beregn antallet af noder på hvert niveau

Lad os først bestemme antallet af noder i det sidste niveau. Ud fra rekursionstræet kan vi udlede dette

• Niveau-0 har 1 (2^0) node
• Niveau-1 har 2 (2^1) noder
• Niveau-2 har 4 (2^2) noder
• Niveau-3 har 8 (2^3) noder

Så niveauet log(n) skal have 2^(log(n)) noder, dvs. n noder.

Trin 5: Opsummer prisen på alle niveauerne

• De samlede omkostninger kan skrives som,
• Samlede omkostninger = Omkostninger for alle niveauer undtagen sidste niveau + Pris for sidste niveau
• Samlede omkostninger = omkostninger for niveau-0 + omkostninger for niveau-1 + omkostninger for niveau-2 +.... + omkostninger for niveau-log(n) + omkostninger for sidste niveau

Prisen for det sidste niveau beregnes separat, fordi det er basissagen, og der ikke foretages sammenlægning på det sidste niveau, så omkostningerne ved at løse et enkelt problem på dette niveau er en konstant værdi. Lad os tage det som O (1).

Lad os sætte værdierne ind i formlerne,

• T(n) = K + 2*K + 4*K + .... + log(n)` gange + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) gange)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) gange + O(n)

Hvis du ser nærmere på ovenstående udtryk, danner det en geometrisk progression (a, ar, ar^2, ar^3 ...... uendelig tid). Summen af ​​GP er givet ved S(N) = a / (r - 1). Her er det første led, og r er det fælles forhold.