Rekursjon er et grunnleggende konsept innen informatikk og matematikk som lar funksjoner kalle seg selv, og muliggjør løsning av komplekse problemer gjennom iterative trinn. En visuell representasjon som vanligvis brukes for å forstå og analysere utførelsen av rekursive funksjoner, er et rekursjonstre. I denne artikkelen vil vi utforske teorien bak rekursjonstrær, deres struktur og deres betydning for å forstå rekursive algoritmer.

Hva er et rekursjonstre?

Et rekursjonstre er en grafisk representasjon som illustrerer utførelsesflyten til en rekursiv funksjon. Den gir en visuell oversikt over rekursive samtaler, og viser fremdriften til algoritmen når den forgrener seg og til slutt når et grunnleggende tilfelle. Trestrukturen hjelper til med å analysere tidskompleksiteten og forstå den rekursive prosessen som er involvert.

Trestruktur

Hver node i et rekursjonstre representerer et bestemt rekursivt anrop. Det første anropet er avbildet øverst, med påfølgende anrop som forgrener seg under det. Treet vokser nedover og danner en hierarkisk struktur. Forgreningsfaktoren til hver node avhenger av antallet rekursive anrop som utføres i funksjonen. I tillegg tilsvarer dybden av treet antall rekursive anrop før man når basistilfellet.

Base Case

Basistilfellet fungerer som termineringsbetingelsen for en rekursiv funksjon. Den definerer punktet der rekursjonen stopper og funksjonen begynner å returnere verdier. I et rekursjonstre er nodene som representerer basistilfellet vanligvis avbildet som bladnoder, siden de ikke resulterer i ytterligere rekursive anrop.

Rekursive anrop

Undernodene i et rekursjonstre representerer de rekursive anropene som gjøres i funksjonen. Hver underordnede node tilsvarer et separat rekursivt kall, noe som resulterer i opprettelse av nye underproblemer. Verdiene eller parameterne som sendes til disse rekursive samtalene kan variere, noe som fører til variasjoner i underproblemenes egenskaper.

Utførelsesflyt:

Å krysse et rekursjonstre gir innsikt i utførelsesflyten til en rekursiv funksjon. Fra det første anropet ved rotnoden, følger vi grenene for å nå påfølgende anrop til vi møter grunntilfellet. Når basistilfellene er nådd, begynner de rekursive anropene å returnere, og deres respektive noder i treet er merket med de returnerte verdiene. Traverseringen fortsetter til hele treet er krysset.

Tidskompleksitetsanalyse

Rekursjonstrær hjelper til med å analysere tidskompleksiteten til rekursive algoritmer. Ved å undersøke strukturen til treet, kan vi bestemme antall rekursive anrop og arbeidet som er utført på hvert nivå. Denne analysen hjelper til med å forstå den generelle effektiviteten til algoritmen og identifisere potensielle ineffektiviteter eller muligheter for optimalisering.

Introduksjon

• Tenk på et program som bestemmer et talls faktorial. Denne funksjonen tar et tall N som input og returnerer faktoren til N som et resultat. Denne funksjonens 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 */ 

• Rekursjon er eksemplifisert ved funksjonen som tidligere ble nevnt. Vi påkaller en funksjon for å bestemme et talls faktorial. Så, gitt en mindre verdi av det samme tallet, kaller denne funksjonen seg selv. Dette fortsetter til vi kommer til det grunnleggende tilfellet, der det ikke er flere funksjonskall.
• Rekursjon er en teknikk for å håndtere kompliserte problemstillinger når utfallet er avhengig av utfallet av mindre tilfeller av samme problem.
• Hvis vi tenker på funksjoner, sies en funksjon å være rekursiv hvis den fortsetter å kalle seg selv inntil den når basistilfellet.
• Enhver rekursiv funksjon har to primære komponenter: basistilfellet og det rekursive trinnet. Vi slutter å gå til den rekursive fasen når vi når den grunnleggende saken. For å forhindre endeløs rekursjon, må basecases være riktig definert og er avgjørende. Definisjonen av uendelig rekursjon er en rekursjon som aldri når basistilfellet. Hvis et program aldri når basistilfellet, vil stackoverflyt fortsette å skje.

Rekursjonstyper

Generelt sett er det to forskjellige former for rekursjon:

• Lineær rekursjon
• Trerekursjon
• Lineær rekursjon

Lineær rekursjon

• En funksjon som kaller seg selv bare én gang hver gang den utføres sies å være lineært rekursiv. En fin illustrasjon av lineær rekursjon er faktoriell funksjon. Navnet 'lineær rekursjon' refererer til det faktum at en lineært rekursiv funksjon tar en lineær mengde tid å utføre.
• Ta en titt 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å funksjonen doSomething(n), godtar den en parameter kalt n og gjør noen beregninger før den kaller opp samme prosedyre en gang til, men med lavere verdier.
• Når metoden doSomething() kalles med argumentverdien n, la oss si at T(n) representerer den totale tiden som trengs for å fullføre beregningen. For dette kan vi også formulere en gjentaksrelasjon, T(n) = T(n-1) + K. K fungerer som en konstant her. Konstant K er inkludert fordi det tar tid for funksjonen å allokere eller de-allokere minne til en variabel eller utføre en matematisk operasjon. Vi bruker K for å definere tiden siden den er så liten og ubetydelig.
• Dette rekursive programmets tidskompleksitet kan ganske enkelt beregnes, siden metoden doSomething() i verste fall kalles n ganger. Formelt sett er funksjonens tidsmessige kompleksitet O(N).

Trerekursjon

• Når du foretar et rekursivt anrop i ditt rekursive tilfelle mer enn én gang, blir det referert til som trerekursjon. En effektiv illustrasjon av trerekursjon er fibonacci-sekvensen. Trerekursive funksjoner opererer i eksponentiell tid; de er ikke lineære i sin tidsmessige kompleksitet.
• Ta en titt 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 forskjellen mellom denne koden og den forrige er at denne ringer til den samme funksjonen med en lavere verdi på n.
• La oss sette T(n) = T(n-1) + T(n-2) + k som gjentakelsesrelasjonen for denne funksjonen. K fungerer som en konstant igjen.
• Når mer enn ett kall til samme funksjon med mindre verdier utføres, er denne typen rekursjon kjent som trerekursjon. Det spennende aspektet er nå: hvor tidkrevende er denne funksjonen?
• Ta en gjetning basert på rekursjonstreet nedenfor for samme funksjon.
  
• Det kan skje for deg at det er utfordrende å estimere tidskompleksiteten ved å se direkte på en rekursiv funksjon, spesielt når det er en trerekursjon. Rekursjonstremetoden er en av flere teknikker for å beregne den tidsmessige kompleksiteten til slike funksjoner. La oss undersøke det nærmere.

Hva er rekursjonstremetoden?

• Gjentakelsesrelasjoner som T(N) = T(N/2) + N eller de to vi dekket tidligere i typen rekursjonsdelen løses ved å bruke rekursjonstre-tilnærmingen. Disse gjentakende relasjonene bruker ofte en skille og hersk-strategi for å løse problemer.
• Det tar tid å integrere svarene på de mindre delproblemene som skapes når et større problem brytes ned i mindre delproblemer.
• Gjentakelsesrelasjonen er for eksempel T(N) = 2 * T(N/2) + O(N) for sammenslåingssortering. Tiden som trengs for å kombinere svarene på to underoppgaver med en kombinert størrelse på T(N/2) er O(N), som også gjelder på implementeringsnivå.
• For eksempel, siden gjentakelsesrelasjonen for binært søk er T(N) = T(N/2) + 1, vet vi at hver iterasjon av binært søk resulterer i et søkerom som er kuttet i to. Når utfallet er bestemt, avslutter vi funksjonen. Gjentakelsesrelasjonen har +1 lagt til fordi dette er en konstant tidsoperasjon.
• Gjentaksrelasjonen T(n) = 2T(n/2) + Kn er en å vurdere. Kn angir hvor lang tid det tar å kombinere svarene på n/2-dimensjonale underoppgaver.
• La oss skildre rekursjonstreet for den nevnte gjentakelsesrelasjonen.

Vi kan trekke noen konklusjoner fra å studere rekursjonstreet ovenfor, inkludert

1. Størrelsen på problemet på hvert nivå er alt som betyr noe for å bestemme verdien av en node. Problemstørrelsen er n på nivå 0, n/2 på nivå 1, n/2 på nivå 2, og så videre.

2. Generelt definerer vi høyden på treet som lik log (n), der n er størrelsen på problemet, og høyden på dette rekursjonstreet er lik antall nivåer i treet. Dette er sant fordi, som vi nettopp har slått fast, brukes del-og-hersk-strategien av gjentakende relasjoner for å løse problemer, og å komme fra problemstørrelse n til problemstørrelse 1 krever ganske enkelt å ta log(n)-trinn.

• Tenk på verdien av N = 16, for eksempel. Hvis vi har lov til å dele N med 2 på hvert trinn, hvor mange trinn kreves for å få N = 1? Tatt i betraktning at vi deler med to på hvert trinn, er det riktige svaret 4, som er verdien av log(16) base 2.

log(16) base 2

log(2^4) base 2

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

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

3. På hvert nivå regnes det andre leddet i gjentakelsen som roten.

Selv om ordet 'tre' vises i navnet på denne strategien, trenger du ikke å være ekspert på trær for å forstå det.

Hvordan bruke et rekursjonstre for å løse gjentakelsesforhold?

Kostnaden for delproblemet i rekursjonstreteknikken er mengden tid som trengs for å løse delproblemet. Derfor, hvis du legger merke til uttrykket 'kostnad' knyttet til rekursjonstreet, refererer det ganske enkelt til hvor lang tid som trengs for å løse et bestemt underproblem.

La oss forstå alle disse trinnene med noen få eksempler.

Eksempel

Tenk på gjentakelsesforholdet,

java-verdi av streng

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

Løsning

Den gitte gjentaksrelasjonen viser følgende egenskaper,

En oppgavestørrelse n er delt inn i to deloppgaver hver med størrelse n/2. Kostnaden for å kombinere løsningene på disse delproblemene er K.

Hver oppgavestørrelse på n/2 er delt inn i to underoppgaver hver med størrelse n/4 og så videre.

På siste nivå vil delproblemstørrelsen reduseres til 1. Med andre ord treffer vi til slutt grunnsaken.

La oss følge trinnene for å løse denne gjentakelsesrelasjonen,

Trinn 1: Tegn rekursjonstreet

Trinn 2: Beregn høyden på treet

Siden vi vet at når vi kontinuerlig deler et tall med 2, kommer det en tid da dette tallet reduseres til 1. Samme som med problemstørrelsen N, anta at etter K divisjoner med 2, blir N lik 1, noe som innebærer, ( n / 2^k) = 1

Her er n / 2^k problemstørrelsen på siste nivå, og den er alltid lik 1.

Nå kan vi enkelt beregne verdien av k fra uttrykket ovenfor ved å ta log() til begge sider. Nedenfor er en mer tydelig avledning,

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øyden på treet er log (n) base 2.

Trinn 3: Beregn kostnadene på hvert nivå

• Kostnad på Nivå-0 = K, to deloppgaver slås sammen.
• Kostnad på Nivå-1 = K + K = 2*K, to deloppgaver slås sammen to ganger.
• Kostnad på Nivå-2 = K + K + K + K = 4*K, to deloppgaver slås sammen fire ganger. og så videre....

Trinn 4: Beregn antall noder på hvert nivå

La oss først bestemme antall noder i det siste nivået. Fra rekursjonstreet kan vi utlede dette

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

Så nivået log(n) bør ha 2^(log(n)) noder, dvs. n noder.

Trinn 5: Oppsummer kostnadene for alle nivåene

• Den totale kostnaden kan skrives som,
• Total kostnad = kostnad for alle nivåer unntatt siste nivå + kostnad for siste nivå
• Total kostnad = kostnad for nivå-0 + kostnad for nivå-1 + kostnad for nivå-2 +.... + kostnad for nivå-log(n) + kostnad for siste nivå

Kostnaden for det siste nivået beregnes separat fordi det er basistilfellet og ingen sammenslåing gjøres på siste nivå, så kostnaden for å løse et enkelt problem på dette nivået er en konstant verdi. La oss ta det som O (1).

La oss sette verdiene inn i formlene,

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

Hvis du ser nærmere på uttrykket ovenfor, danner det en geometrisk progresjon (a, ar, ar^2, ar^3 ...... uendelig tid). Summen av GP er gitt ved S(N) = a / (r - 1). Her er det første leddet og r er det vanlige forholdet.