Hvad er rekursion?
Den proces, hvor en funktion kalder sig selv direkte eller indirekte, kaldes rekursion, og den tilsvarende funktion kaldes en rekursiv funktion. Ved hjælp af en rekursiv algoritme kan visse problemer løses ganske nemt. Eksempler på sådanne problemer er Towers of Hanoi (TOH) , Inorder/Preorder/Postorder Trægennemgange , DFS af Graph osv. En rekursiv funktion løser et bestemt problem ved at kalde en kopi af sig selv og løse mindre underopgaver af de originale problemer. Mange flere rekursive opkald kan genereres efter behov. Det er vigtigt at vide, at vi skal give en bestemt sag for at afslutte denne rekursionsproces. Så vi kan sige, at hver gang kalder funktionen sig selv med en enklere version af det oprindelige problem.

Behov for rekursion

Rekursion er en fantastisk teknik, ved hjælp af hvilken vi kan reducere længden af ​​vores kode og gøre det lettere at læse og skrive. Det har visse fordele i forhold til iterationsteknikken, som vil blive diskuteret senere. En opgave, der kan defineres med sin lignende delopgave, rekursion er en af ​​de bedste løsninger til den. For eksempel; Et nummers faktor.

Egenskaber ved rekursion:

• Udfører de samme handlinger flere gange med forskellige input.
• I hvert trin prøver vi mindre input for at gøre problemet mindre.
• Grundtilstand er nødvendig for at stoppe rekursionen, ellers vil der opstå uendelig løkke.

Algoritme: Trin

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 fortolkning

Lad os overveje et problem, som en programmør har for at bestemme summen af ​​første n naturlige tal, der er flere måder at gøre det på, men den enkleste tilgang er simpelthen at tilføje tallene fra 1 til n. Så funktionen ser simpelthen sådan ud,

tilgang(1) – Du skal blot tilføje én efter én

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

men der er en anden matematisk tilgang til at repræsentere dette,

tilgang(2) – Rekursiv addering

f(n) = 1 n=1

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

Der er en simpel forskel mellem tilgang (1) og tilgang (2), og det er i tilgang (2) funktionen f( ) selv kaldes inde i funktionen, så dette fænomen kaldes rekursion, og funktionen, der indeholder rekursion, kaldes rekursiv funktion, i slutningen er dette et fantastisk værktøj i hånden af ​​programmører til at kode nogle problemer meget nemmere og effektivt vej.

Hvordan gemmes rekursive funktioner i hukommelsen?

Rekursion bruger mere hukommelse, fordi den rekursive funktion tilføjer til stakken med hvert rekursivt opkald og beholder værdierne der, indtil opkaldet er afsluttet. Den rekursive funktion bruger LIFO (SIDST IN FØRST UD) struktur ligesom stakdatastrukturen. stak-data-struktur/

Hvad er grundtilstanden ved rekursion?
I det rekursive program gives løsningen på basissagen, og løsningen på det større problem udtrykkes i form af mindre problemer.

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

I ovenstående eksempel defineres basistilfældet for n <= 1, og den større værdi af et tal kan løses ved at konvertere til et mindre, indtil basistilfældet er nået.

Hvordan løses et bestemt problem ved hjælp af rekursion?
Ideen er at repræsentere et problem i form af et eller flere mindre problemer, og tilføje en eller flere basisbetingelser, der stopper rekursionen. For eksempel beregner vi factorial n, hvis vi kender factorial af (n-1). Grundtilfældet for factorial ville være n = 0. Vi returnerer 1, når n = 0.

Hvorfor opstår Stack Overflow-fejl i rekursion?
Hvis basistilfældet ikke nås eller ikke er defineret, kan der opstå et stakoverløbsproblem. Lad os tage et eksempel for at 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) kaldes, vil det kalde fakta(9), fakta(8), fakta(7) og så videre, men tallet vil aldrig nå 100. Så grundtilfældet er ikke nået. Hvis hukommelsen er opbrugt af disse funktioner på stakken, vil det forårsage en stak-overløbsfejl.

Hvad er forskellen mellem direkte og indirekte rekursion?
En funktion sjov kaldes direkte rekursiv, hvis den kalder den samme funktion sjov. En funktion sjov kaldes indirekte rekursiv, hvis den kalder en anden funktion siger fun_new og fun_new kalder sjov direkte eller indirekte. Forskellen mellem direkte og indirekte rekursion er blevet illustreret i tabel 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... }>

Hvad er forskellen mellem tailed og non-tailed rekursion?
En rekursiv funktion er halerekursiv, når et rekursivt kald er det sidste, der udføres af funktionen. Se venligst halerekursionsartikel for detaljer.

Hvordan allokeres hukommelse til forskellige funktionskald i rekursion?
Når en funktion kaldes fra main(), allokeres hukommelsen til den på stakken. En rekursiv funktion kalder sig selv, hukommelsen for en kaldt funktion allokeres oven på hukommelsen allokeret til den kaldende funktion, og en anden kopi af lokale variabler oprettes for hvert funktionskald. Når basistilfældet er nået, returnerer funktionen sin værdi til den funktion, som den kaldes af, og hukommelsen de-allokeres, og processen fortsætter.
Lad os tage eksemplet på, hvordan rekursion virker ved at tage en simpel funktion.

CPP

>

>

Java

javascript globale variabler

>

>

Python3

>

>

C#

>

>

PHP

>

>

Javascript

>

>

3 2 1 1 2 3>

Tidskompleksitet: O(1)
Hjælpeplads: O(1)

Hvornår printFun(3) kaldes fra main(), er hukommelse allokeret til printFun(3) og en lokal variabeltest initialiseres til 3 og sætning 1 til 4 skubbes på stakken som vist i diagrammet nedenfor. Den udskriver først '3'. I erklæring 2, printFun(2) kaldes og hukommelse er allokeret til printFun(2) og en lokal variabeltest initialiseres til 2 og sætning 1 til 4 skubbes ind i stakken. Tilsvarende printFun(2) opkald printFun(1) og printFun(1) opkald printFun(0) . printFun(0) går til hvis erklæring og det vender tilbage til printFun(1) . De resterende udsagn af printFun(1) udføres, og det vender tilbage til printFun(2) og så videre. I outputtet udskrives værdier fra 3 til 1, og derefter udskrives 1 til 3. Hukommelsesstakken er vist i diagrammet nedenfor.

Rekursion VS Iteration

Lad os nu diskutere et par praktiske problemer, som kan løses ved at bruge rekursion og forstå dens grundlæggende funktion. For grundlæggende forståelse, læs venligst følgende artikler.
Grundlæggende forståelse af rekursion.
Opgave 1: Skriv en program- og gentagelsesrelation for at finde Fibonacci-serien af ​​n hvor n>2 .
Matematisk ligning:

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

Gentagelsesforhold:

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>

Implementering:

C++

>

>

C

>

>

Java

vælg fra flere tabeller i sql

>

>

Python3

>

>

C#

>

>

Javascript

>

>

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

Tidskompleksitet: O(2ⁿ)
Hjælpeplads: På)

Her er det rekursive træ til input 5, som viser et klart billede af, hvordan et stort problem kan løses til mindre.
fib(n) er en Fibonacci-funktion. Tidskompleksiteten af ​​det givne program kan afhænge af funktionskaldet.

fib(n) -> niveau CBT (UB) -> 2^n-1 noder -> 2^n funktionskald -> 2^n*O(1) -> T(n) = O(2^n)

For bedste tilfælde.

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

Arbejder:

Opgave 2: Skriv en program- og gentagelsesrelation for at finde faktoren af ​​n hvor n>2 .
Matematisk ligning:

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

Gentagelsesforhold:

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

Rekursivt program:
Input: n = 5
Produktion:
faktor 5 er: 120
Implementering:

C++

>

>

C

simpelt java-program

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

factorial of 5 is: 120>

Tidskompleksitet: På)
Hjælpeplads: På)

Arbejder:

Diagram over faktoriel rekursionsfunktion for brugerinput 5.

Eksempel: Reelle anvendelser af rekursion i virkelige problemer

Rekursion er en kraftfuld teknik, der har mange anvendelser inden for datalogi og programmering. Her er nogle af de almindelige anvendelser af rekursion:

Træ- og grafgennemgang: Rekursion bruges ofte til at krydse og søge i datastrukturer såsom træer og grafer. Rekursive algoritmer kan bruges til at udforske alle knudepunkter eller hjørner i et træ eller en graf på en systematisk måde. Sorteringsalgoritmer: Rekursive algoritmer bruges også til sorteringsalgoritmer såsom quicksort og merge sort. Disse algoritmer bruger rekursion til at opdele dataene i mindre underarrays eller underlister, sortere dem og derefter flette dem sammen igen. Del-og-hersk-algoritmer : Mange algoritmer, der bruger en del-og-hersk-tilgang, såsom den binære søgealgoritme, bruger rekursion til at opdele problemet i mindre underproblemer. Fraktalgenerering: Fraktalformer og mønstre kan genereres ved hjælp af rekursive algoritmer. For eksempel genereres Mandelbrot-sættet ved gentagne gange at anvende en rekursiv formel på komplekse tal. Tilbagesporingsalgoritmer : Tilbagesporingsalgoritmer bruges til at løse problemer, der involverer at træffe en række beslutninger, hvor hver beslutning afhænger af de foregående. Disse algoritmer kan implementeres ved hjælp af rekursion for at udforske alle mulige stier og gå tilbage, når en løsning ikke findes. Memoisering : Memoisering er en teknik, der involverer lagring af resultaterne af dyre funktionskald og returnering af det cachelagrede resultat, når de samme input forekommer igen. Memoisering kan implementeres ved hjælp af rekursive funktioner til at beregne og cache resultaterne af underproblemer.

Dette er blot nogle få eksempler på de mange anvendelser af rekursion inden for datalogi og programmering. Rekursion er et alsidigt og kraftfuldt værktøj, der kan bruges til at løse mange forskellige typer problemer.

Forklaring: et rigtigt eksempel på rekursion:

Rekursion er en programmeringsteknik, der involverer en funktion, der kalder sig selv. Det kan være et kraftfuldt værktøj til at løse komplekse problemer, men det kræver også omhyggelig implementering for at undgå uendelige loops og stak-overløb.

Her er et eksempel på implementering af rekursion i Python:

C++

>

>

Java

>

>

Python3

>

>

C#

int til char java

>

>

Javascript

>

>

120>

I dette eksempel definerer vi en funktion kaldet faktoriel, der tager et heltal n som input. Funktionen bruger rekursion til at beregne faktoren af ​​n (dvs. produktet af alle positive heltal op til n).

Faktorialfunktionen kontrollerer først, om n er 0 eller 1, som er basistilfældene. Hvis n er 0 eller 1, returnerer funktionen 1, da 0! og 1! er begge 1.

Hvis n er større end 1, går funktionen ind i det rekursive tilfælde. Den kalder sig selv med n-1 som argument og multiplicerer resultatet med n. Dette beregner n! ved rekursiv beregning (n-1)!.

Det er vigtigt at bemærke, at rekursion kan være ineffektivt og føre til stak-overløb, hvis det ikke bruges omhyggeligt. Hvert funktionskald tilføjer en ny ramme til opkaldsstakken, hvilket kan få stakken til at vokse sig for stor, hvis rekursionen er for dyb. Derudover kan rekursion gøre koden sværere at forstå og fejlfinde, da det kræver, at man tænker på flere niveauer af funktionskald.

Men rekursion kan også være et stærkt værktøj til at løse komplekse problemer, især dem, der involverer at opdele et problem i mindre delproblemer. Når den bruges korrekt, kan rekursion gøre koden mere elegant og lettere at læse.

Hvad er ulemperne ved rekursiv programmering frem for iterativ programmering?
Bemærk, at både rekursive og iterative programmer har de samme problemløsningsevner, dvs. at hvert rekursivt program kan skrives iterativt og omvendt er også sandt. Det rekursive program har større pladsbehov end det iterative program, da alle funktioner forbliver i stakken, indtil basissagen er nået. Det har også større tidskrav på grund af funktionskald og overhead.

På grund af den mindre kodelængde er koderne desuden svære at forstå, og derfor skal der udvises ekstra forsigtighed, mens koden skrives. Computeren kan løbe tør for hukommelse, hvis de rekursive opkald ikke kontrolleres korrekt.

Hvad er fordelene ved rekursiv programmering frem for iterativ programmering?
Rekursion giver en ren og enkel måde at skrive kode på. Nogle problemer er i sagens natur rekursive som trægennemgange, Hanois tårn osv. For sådanne problemer foretrækkes det at skrive rekursiv kode. Vi kan også skrive sådanne koder iterativt ved hjælp af en stak datastruktur. Se f.eks. Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

Resumé af rekursion:

• Der er to typer tilfælde i rekursion, dvs. rekursivt tilfælde og et basistilfælde.
• Grundtilfældet bruges til at afslutte den rekursive funktion, når tilfældet viser sig at være sandt.
• Hvert rekursivt kald laver en ny kopi af denne metode i stakhukommelsen.
• Uendelig rekursion kan føre til at løbe tør for stakhukommelse.
• Eksempler på rekursive algoritmer: Merge Sort, Hurtig sortering, Tower of Hanoi, Fibonacci Series, Facttorial Problem osv.

Outputbaserede øvelsesproblemer for begyndere:
Øvelsesspørgsmål til rekursion | Sæt 1
Øvelsesspørgsmål til rekursion | Sæt 2
Øvelsesspørgsmål til rekursion | Sæt 3
Øvelsesspørgsmål til rekursion | Sæt 4
Øvelsesspørgsmål til rekursion | Sæt 5
Øvelsesspørgsmål til rekursion | Sæt 6
Øvelsesspørgsmål til rekursion | Sæt 7
Quiz om rekursion
Kodningspraksis på rekursion:
Alle artikler om rekursion
Problemer med rekursiv praksis med løsninger