Hva er rekursjon?
Prosessen der en funksjon kaller seg selv direkte eller indirekte kalles rekursjon og den tilsvarende funksjonen kalles en rekursiv funksjon. Ved å bruke en rekursiv algoritme kan visse problemer løses ganske enkelt. Eksempler på slike problemer er Towers of Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS av Graph , etc. En rekursiv funksjon løser et bestemt problem ved å kalle en kopi av seg selv og løse mindre delproblemer av de originale problemene. Mange flere rekursive anrop kan genereres etter behov. Det er viktig å vite at vi bør gi en bestemt sak for å avslutte denne rekursjonsprosessen. Så vi kan si at hver gang funksjonen kaller seg selv med en enklere versjon av det opprinnelige problemet.

Behov for rekursjon

Rekursjon er en fantastisk teknikk ved hjelp av hvilken vi kan redusere lengden på koden vår og gjøre det lettere å lese og skrive. Det har visse fordeler i forhold til iterasjonsteknikken som vil bli diskutert senere. En oppgave som kan defineres med sin lignende deloppgave, rekursjon er en av de beste løsningene for den. For eksempel; Faktoren til et tall.

Egenskaper ved rekursjon:

• Utfører de samme operasjonene flere ganger med forskjellige innganger.
• I hvert trinn prøver vi mindre input for å gjøre problemet mindre.
• Grunntilstand er nødvendig for å stoppe rekursjonen ellers vil det oppstå uendelig sløyfe.

Algoritme: Trinn

The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>

En matematisk tolkning

La oss vurdere et problem som en programmerer har for å bestemme summen av første n naturlige tall, det er flere måter å gjøre det på, men den enkleste tilnærmingen er ganske enkelt å legge til tallene fra 1 til n. Så funksjonen ser rett og slett slik ut,

tilnærming(1) – Bare å legge til en etter en

f(n) = 1 + 2 + 3 +……..+ n

men det er en annen matematisk tilnærming for å representere dette,

tilnærming(2) – Rekursiv addering

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

Det er en enkel forskjell mellom tilnærmingen (1) og tilnærmingen (2), og det er i tilnærming (2) funksjonen f( ) selv kalles inne i funksjonen, så dette fenomenet heter rekursjon, og funksjonen som inneholder rekursjon kalles rekursiv funksjon, på slutten er dette et flott verktøy i hendene til programmerere for å kode noen problemer på mye enklere og effektivt vei.

Hvordan lagres rekursive funksjoner i minnet?

Rekursjon bruker mer minne, fordi den rekursive funksjonen legger til stabelen med hvert rekursivt anrop, og beholder verdiene der til anropet er ferdig. Den rekursive funksjonen bruker LIFO (SISTE INN FØRST UT) struktur akkurat som stabeldatastrukturen. stack-data-structure/

Hva er grunntilstanden ved rekursjon?
I det rekursive programmet er løsningen på grunntilfellet gitt og løsningen på det større problemet uttrykkes i form av mindre problemer.

int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }>

I eksemplet ovenfor er grunntilfellet for n <= 1 definert, og den største verdien av et tall kan løses ved å konvertere til et mindre til grunntilfellet er nådd.

Hvordan løses et bestemt problem ved hjelp av rekursjon?
Tanken er å representere et problem i form av en eller flere mindre problemer, og legge til en eller flere grunnbetingelser som stopper rekursjonen. For eksempel beregner vi faktorial n hvis vi kjenner faktorialen til (n-1). Grunnlaget for faktoriell vil være n = 0. Vi returnerer 1 når n = 0.

Hvorfor oppstår Stack Overflow-feil i rekursjon?
Hvis basistilfellet ikke nås eller ikke er definert, kan stabeloverløpsproblemet oppstå. La oss ta et eksempel for å forstå dette.

int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }>

Hvis fakta(10) kalles, vil det kalle fakta(9), fakta(8), fakta(7), og så videre, men tallet vil aldri nå 100. Så grunntilfellet er ikke nådd. Hvis minnet er oppbrukt av disse funksjonene på stabelen, vil det forårsake en stabeloverløpsfeil.

Hva er forskjellen mellom direkte og indirekte rekursjon?
En funksjon moro kalles direkte rekursiv hvis den kaller den samme funksjonen moro. En funksjon moro kalles indirekte rekursiv hvis den kaller en annen funksjon si fun_new og fun_new kaller moro direkte eller indirekte. Forskjellen mellom direkte og indirekte rekursjon er illustrert i tabell 1.

 // An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }>

Hva er forskjellen mellom tailed og non-tailed rekursjon?
En rekursiv funksjon er halerekursiv når et rekursivt kall er det siste som utføres av funksjonen. Vennligst referer halerekursjonsartikkel for detaljer.

Hvordan tildeles minne til ulike funksjonskall i rekursjon?
Når en funksjon kalles fra main(), blir minnet allokert til den på stabelen. En rekursiv funksjon kaller seg selv, minnet for en kalt funksjon blir allokert på toppen av minnet som er allokert til den kallende funksjonen, og en annen kopi av lokale variabler opprettes for hvert funksjonskall. Når basistilfellet er nådd, returnerer funksjonen sin verdi til funksjonen den kalles av, og minnet blir deallokert og prosessen fortsetter.
La oss ta eksempelet på hvordan rekursjon fungerer ved å ta en enkel funksjon.

CPP

>

>

Java

string.format i java

>

>

Python3

>

>

C#

>

>

PHP

>

>

Javascript

>

>

3 2 1 1 2 3>

Tidskompleksitet: O(1)
Hjelpeplass: O(1)

Når printFun(3) kalles fra main(), minne er allokert til printFun(3) og en lokal variabeltest initialiseres til 3 og setning 1 til 4 skyves på stabelen som vist i diagrammet nedenfor. Den skriver først ut '3'. I uttalelse 2, printFun(2) kalles og minne er allokert til printFun(2) og en lokal variabeltest initialiseres til 2 og setning 1 til 4 skyves inn i stabelen. På samme måte, printFun(2) samtaler printFun(1) og printFun(1) samtaler printFun(0) . printFun(0) går til hvis uttalelse og den går tilbake til printFun(1) . De resterende uttalelsene av printFun(1) blir utført og den går tilbake til printFun(2) og så videre. I utgangen skrives verdier fra 3 til 1 ut og deretter 1 til 3 skrives ut. Minnestakken er vist i diagrammet nedenfor.

Rekursjon VS Iterasjon

La oss nå diskutere noen få praktiske problemer som kan løses ved å bruke rekursjon og forstå dens grunnleggende virkemåte. For grunnleggende forståelse, vennligst les følgende artikler.
Grunnleggende forståelse av rekursjon.
Oppgave 1: Skriv et program- og gjentakelsesforhold for å finne Fibonacci-serien av n hvor n>2 .
Matematisk ligning:

n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>

Gjentakelsesforhold:

T(n) = T(n-1) + T(n-2) + O(1)>

Rekursivt program:

 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>

Gjennomføring:

C++

>

>

C

>

>

Java

hvordan åpne en fil med java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Fibonacci series of 5 numbers is: 0 1 1 2 3>

Tidskompleksitet: O(2ⁿ)
Hjelpeplass: På)

Her er det rekursive treet for input 5 som viser et klart bilde av hvordan et stort problem kan løses til mindre.
fib(n) er en Fibonacci-funksjon. Tidskompleksiteten til det gitte programmet kan avhenge av funksjonskallet.

fib(n) -> nivå CBT (UB) -> 2^n-1 noder -> 2^n funksjonsanrop -> 2^n*O(1) -> T(n) = O(2^n)

For beste tilfelle.

T(n) = ?(2^n2)>

Arbeider:

Oppgave 2: Skriv et program og gjentakelsesrelasjon for å finne faktoren til n hvor n>2 .
Matematisk ligning:

1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>

Gjentakelsesforhold:

T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>

Rekursivt program:
Inndata: n = 5
Produksjon:
faktor på 5 er: 120
Gjennomføring:

C++

>

>

C

hvordan oppgradere java

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

factorial of 5 is: 120>

Tidskompleksitet: På)
Hjelpeplass: På)

Arbeider:

Diagram over faktoriell rekursjonsfunksjon for brukerinndata 5.

Eksempel: Reelle anvendelser av rekursjon i reelle problemer

Rekursjon er en kraftig teknikk som har mange applikasjoner innen informatikk og programmering. Her er noen av de vanlige anvendelsene av rekursjon:

Tre- og grafgjennomgang : Rekursjon brukes ofte for å krysse og søke i datastrukturer som trær og grafer. Rekursive algoritmer kan brukes til å utforske alle noder eller toppunkter i et tre eller en graf på en systematisk måte. Sorteringsalgoritmer : Rekursive algoritmer brukes også i sorteringsalgoritmer som quicksort og merge sort. Disse algoritmene bruker rekursjon for å dele dataene inn i mindre undergrupper eller underlister, sortere dem og deretter slå dem sammen igjen. Del-og-hersk-algoritmer : Mange algoritmer som bruker en del-og-hersk-tilnærming, for eksempel den binære søkealgoritmen, bruker rekursjon for å bryte ned problemet i mindre delproblemer. Fraktalgenerering: Fraktalformer og mønstre kan genereres ved hjelp av rekursive algoritmer. For eksempel genereres Mandelbrot-settet ved gjentatte ganger å bruke en rekursiv formel på komplekse tall. Tilbakesporingsalgoritmer : Tilbakesporingsalgoritmer brukes til å løse problemer som innebærer å ta en sekvens av beslutninger, der hver beslutning avhenger av de forrige. Disse algoritmene kan implementeres ved hjelp av rekursjon for å utforske alle mulige veier og gå tilbake når en løsning ikke blir funnet. Memoisering : Memoisering er en teknikk som innebærer å lagre resultatene av dyre funksjonskall og returnere det bufrede resultatet når de samme inngangene skjer igjen. Memoisering kan implementeres ved å bruke rekursive funksjoner for å beregne og cache resultatene av underproblemer.

Dette er bare noen få eksempler på mange anvendelser av rekursjon innen informatikk og programmering. Rekursjon er et allsidig og kraftig verktøy som kan brukes til å løse mange forskjellige typer problemer.

Forklaring: ett ekte eksempel på rekursjon:

Rekursjon er en programmeringsteknikk som innebærer at en funksjon kaller seg selv. Det kan være et kraftig verktøy for å løse komplekse problemer, men det krever også nøye implementering for å unngå uendelige løkker og stabeloverløp.

Her er et eksempel på implementering av rekursjon i Python:

C++

>

>

Java

>

>

Python3

>

>

C#

type i java

>

>

Javascript

>

>

120>

I dette eksemplet definerer vi en funksjon kalt faktoriell som tar et heltall n som input. Funksjonen bruker rekursjon for å beregne faktorialet til n (dvs. produktet av alle positive heltall opp til n).

Faktorialfunksjonen sjekker først om n er 0 eller 1, som er grunntilfellene. Hvis n er 0 eller 1, returnerer funksjonen 1, siden 0! og 1! er begge 1.

Hvis n er større enn 1, går funksjonen inn i det rekursive tilfellet. Den kaller seg selv med n-1 som argument og multipliserer resultatet med n. Dette beregner n! ved rekursiv beregning (n-1)!.

Det er viktig å merke seg at rekursjon kan være ineffektivt og føre til stabeloverflyt hvis den ikke brukes forsiktig. Hvert funksjonskall legger til en ny ramme til anropsstakken, noe som kan føre til at stabelen blir for stor hvis rekursjonen er for dyp. I tillegg kan rekursjon gjøre koden vanskeligere å forstå og feilsøke, siden den krever å tenke på flere nivåer av funksjonskall.

Imidlertid kan rekursjon også være et kraftig verktøy for å løse komplekse problemer, spesielt de som involverer å dele et problem ned i mindre delproblemer. Ved riktig bruk kan rekursjon gjøre koden mer elegant og lettere å lese.

Hva er ulempene med rekursiv programmering fremfor iterativ programmering?
Merk at både rekursive og iterative programmer har samme problemløsningsevne, dvs. at hvert rekursivt program kan skrives iterativt og omvendt er også sant. Det rekursive programmet har større plassbehov enn det iterative programmet, da alle funksjoner vil forbli i stabelen til basistilfellet er nådd. Den har også større tidskrav på grunn av funksjonskall og returkostnader.

Dessuten, på grunn av den mindre lengden på koden, er kodene vanskelige å forstå, og derfor må det utvises ekstra forsiktighet mens du skriver koden. Datamaskinen kan gå tom for minne hvis de rekursive anropene ikke kontrolleres ordentlig.

Hva er fordelene med rekursiv programmering fremfor iterativ programmering?
Rekursjon gir en ren og enkel måte å skrive kode på. Noen problemer er iboende rekursive som trekryssinger, Tower of Hanoi , etc. For slike problemer er det foretrukket å skrive rekursiv kode. Vi kan skrive slike koder også iterativt ved hjelp av en stabeldatastruktur. Se for eksempel Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

Sammendrag av rekursjon:

• Det er to typer tilfeller i rekursjon, dvs. rekursivt tilfelle og et basistilfelle.
• Grunnfallet brukes til å avslutte den rekursive funksjonen når tilfellet viser seg å være sant.
• Hvert rekursivt kall lager en ny kopi av den metoden i stabelminnet.
• Uendelig rekursjon kan føre til å gå tom for stabelminne.
• Eksempler på rekursive algoritmer: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factory Problem, etc.

Utgangsbaserte øvingsproblemer for nybegynnere:
Øvingsspørsmål for rekursjon | Sett 1
Øvingsspørsmål for rekursjon | Sett 2
Øvingsspørsmål for rekursjon | Sett 3
Øvingsspørsmål for rekursjon | Sett 4
Øvingsspørsmål for rekursjon | Sett 5
Øvingsspørsmål for rekursjon | Sett 6
Øvingsspørsmål for rekursjon | Sett 7
Quiz om rekursjon
Kodingspraksis på rekursjon:
Alle artikler om rekursjon
Problemer med rekursiv praksis med løsninger