Rekursion är ett grundläggande begrepp inom datavetenskap och matematik som tillåter funktioner att anropa sig själva, vilket möjliggör lösning av komplexa problem genom iterativa steg. En visuell representation som vanligtvis används för att förstå och analysera exekveringen av rekursiva funktioner är ett rekursionsträd. I den här artikeln kommer vi att utforska teorin bakom rekursionsträd, deras struktur och deras betydelse för att förstå rekursiva algoritmer.

Vad är ett rekursionsträd?

Ett rekursionsträd är en grafisk representation som illustrerar exekveringsflödet av en rekursiv funktion. Det ger en visuell uppdelning av rekursiva samtal, som visar algoritmens utveckling när den förgrenar sig och så småningom når ett basfall. Trädstrukturen hjälper till att analysera tidskomplexiteten och förstå den inblandade rekursiva processen.

gör medan loop i java

Trädstruktur

Varje nod i ett rekursionsträd representerar ett speciellt rekursivt anrop. Det första samtalet visas överst, med efterföljande samtal som förgrenar sig under det. Trädet växer nedåt och bildar en hierarkisk struktur. Förgreningsfaktorn för varje nod beror på antalet rekursiva anrop som görs inom funktionen. Dessutom motsvarar trädets djup antalet rekursiva anrop innan det når basfallet.

Basfallet

Basfallet fungerar som termineringsvillkoret för en rekursiv funktion. Den definierar punkten där rekursionen slutar och funktionen börjar returnera värden. I ett rekursionsträd är noderna som representerar basfallet vanligtvis avbildade som lövnoder, eftersom de inte resulterar i ytterligare rekursiva anrop.

Rekursiva samtal

De underordnade noderna i ett rekursionsträd representerar de rekursiva anrop som görs inom funktionen. Varje barnnod motsvarar ett separat rekursivt anrop, vilket resulterar i skapandet av nya underproblem. Värdena eller parametrarna som skickas till dessa rekursiva anrop kan skilja sig, vilket leder till variationer i underproblemens egenskaper.

Utförandeflöde:

Att korsa ett rekursionsträd ger insikter i exekveringsflödet för en rekursiv funktion. Med start från det första anropet vid rotnoden följer vi grenarna för att nå efterföljande anrop tills vi stöter på basfallet. När basfallen nås börjar de rekursiva anropen att återkomma, och deras respektive noder i trädet markeras med de returnerade värdena. Traverseringen fortsätter tills hela trädet har passerats.

Tidskomplexitetsanalys

Rekursionsträd hjälper till att analysera tidskomplexiteten hos rekursiva algoritmer. Genom att undersöka trädets struktur kan vi bestämma antalet rekursiva anrop som gjorts och det arbete som utförs på varje nivå. Denna analys hjälper till att förstå den övergripande effektiviteten av algoritmen och identifiera eventuella ineffektiviteter eller möjligheter till optimering.

Introduktion

• Tänk på ett program som bestämmer ett tals faktor. Den här funktionen tar ett tal N som inmatning och returnerar som ett resultat faktorn av N. Denna funktions pseudokod kommer att likna,

 // 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 exemplifieras av funktionen som tidigare nämndes. Vi anropar en funktion för att bestämma ett tals faktor. Sedan, givet ett lägre värde av samma nummer, anropar denna funktion sig själv. Detta fortsätter tills vi når grundfallet, där det inte finns fler funktionsanrop.
• Rekursion är en teknik för att hantera komplicerade problem när utfallet är beroende av utfallet av mindre instanser av samma problem.
• Om vi ​​tänker på funktioner sägs en funktion vara rekursiv om den fortsätter att anropa sig själv tills den når basfallet.
• Varje rekursiv funktion har två primära komponenter: basfallet och det rekursiva steget. Vi slutar gå till den rekursiva fasen när vi väl når grundfallet. För att förhindra ändlös rekursion måste basfallen definieras korrekt och är avgörande. Definitionen av oändlig rekursion är en rekursion som aldrig når basfallet. Om ett program aldrig når basfallet kommer stackoverflow att fortsätta att inträffa.

Rekursionstyper

Generellt sett finns det två olika former av rekursion:

• Linjär rekursion
• Trädrekursion
• Linjär rekursion

Linjär rekursion

• En funktion som anropar sig själv bara en gång varje gång den körs sägs vara linjärt rekursiv. En bra illustration av linjär rekursion är den faktoriella funktionen. Namnet 'linjär rekursion' syftar på det faktum att en linjärt rekursiv funktion tar en linjär tid att utföra.
• Ta en titt på pseudokoden nedan:

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

• Om vi ​​tittar på funktionen doSomething(n), accepterar den en parameter som heter n och gör några beräkningar innan den anropar samma procedur en gång till men med lägre värden.
• När metoden doSomething() anropas med argumentvärdet n, låt oss säga att T(n) representerar den totala tid som krävs för att slutföra beräkningen. För detta kan vi också formulera en återfallsrelation, T(n) = T(n-1) + K. K fungerar som en konstant här. Konstant K ingår eftersom det tar tid för funktionen att allokera eller avallokera minne till en variabel eller utföra en matematisk operation. Vi använder K för att definiera tiden eftersom den är så liten och obetydlig.
• Det här rekursiva programmets tidskomplexitet kan enkelt beräknas eftersom metoden doSomething() i värsta fall kallas n gånger. Formellt sett är funktionens tidsmässiga komplexitet O(N).

Trädrekursion

• När du gör ett rekursivt anrop i ditt rekursiva fall mer än en gång, kallas det för trädrekursion. En effektiv illustration av trädrekursion är fibonacci-sekvensen. Träds rekursiva funktioner fungerar i exponentiell tid; de är inte linjära i sin tidsmässiga komplexitet.
• Ta en titt på pseudokoden nedan,

 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 enda skillnaden mellan den här koden och den föregående är att den här gör ytterligare ett anrop till samma funktion med ett lägre värde på n.
• Låt oss sätta T(n) = T(n-1) + T(n-2) + k som återkommande relation för denna funktion. K fungerar som en konstant igen.
• När mer än ett anrop till samma funktion med mindre värden utförs kallas denna typ av rekursion som trädrekursion. Den spännande aspekten är nu: hur tidskrävande är denna funktion?
• Ta en gissning baserad på rekursionsträdet nedan för samma funktion.
  
• Det kan falla dig in att det är utmanande att uppskatta tidskomplexiteten genom att titta direkt på en rekursiv funktion, särskilt när det är en trädrekursion. Rekursionsträdmetoden är en av flera tekniker för att beräkna den tidsmässiga komplexiteten hos sådana funktioner. Låt oss undersöka det mer i detalj.

Vad är rekursionsträdmetoden?

• Återkommande relationer som T(N) = T(N/2) + N eller de två vi behandlade tidigare i avsnittet om typer av rekursion löses med hjälp av rekursionsträdsmetoden. Dessa återkommande relationer använder ofta en splittra och erövra strategi för att ta itu med problem.
• Det tar tid att integrera svaren på de mindre delproblemen som skapas när ett större problem bryts ner i mindre delproblem.
• Upprepningsrelationen är till exempel T(N) = 2 * T(N/2) + O(N) för sammanfogningssorteringen. Den tid som behövs för att kombinera svaren på två delproblem med en kombinerad storlek på T(N/2) är O(N), vilket även gäller på implementeringsnivå.
• Till exempel, eftersom återfallsrelationen för binär sökning är T(N) = T(N/2) + 1, vet vi att varje iteration av binär sökning resulterar i ett sökutrymme som är halverat. När resultatet är fastställt avslutar vi funktionen. Upprepningsrelationen har lagts till +1 eftersom detta är en konstant tidsoperation.
• Återkommande relationen T(n) = 2T(n/2) + Kn är en att ta hänsyn till. Kn anger hur lång tid som krävs för att kombinera svaren på n/2-dimensionella delproblem.
• Låt oss avbilda rekursionsträdet för ovannämnda återfallsrelation.

Vi kan dra några slutsatser från att studera rekursionsträdet ovan, inklusive

1. Storleken på problemet på varje nivå är allt som spelar roll för att bestämma värdet på en nod. Emissionsstorleken är n på nivå 0, n/2 på nivå 1, n/2 på nivå 2, och så vidare.

2. I allmänhet definierar vi trädets höjd som lika med log (n), där n är problemets storlek och höjden på detta rekursionsträd är lika med antalet nivåer i trädet. Detta är sant eftersom, som vi just fastställde, dela-och-härska-strategin används av återkommande relationer för att lösa problem, och att komma från problemstorlek n till problemstorlek 1 kräver helt enkelt log(n)-steg.

• Tänk på värdet av N = 16, till exempel. Om vi ​​tillåts dividera N med 2 vid varje steg, hur många steg krävs för att få N = 1? Med tanke på att vi dividerar med två i varje steg är det korrekta svaret 4, vilket är värdet på log(16) bas 2.

log(16) bas 2

log(2^4) bas 2

4 * log(2) bas 2, eftersom log(a) bas a = 1

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

3. På varje nivå betraktas den andra termen i upprepningen som roten.

regressionsuttryck i java

Även om ordet 'träd' förekommer i denna strategis namn, behöver du inte vara expert på träd för att förstå det.

java matte pow

Hur man använder ett rekursionsträd för att lösa återfallsrelationer?

Kostnaden för delproblemet i rekursionsträdtekniken är den tid som behövs för att lösa delproblemet. Därför, om du märker frasen 'kostnad' kopplat till rekursionsträdet, hänvisar det helt enkelt till hur lång tid som behövs för att lösa ett visst delproblem.

Låt oss förstå alla dessa steg med några exempel.

Exempel

Tänk på återfallsrelationen,

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

Lösning

Den givna återfallsrelationen visar följande egenskaper,

Ett problemstorlek n är uppdelat i två delproblem vardera med storlek n/2. Kostnaden för att kombinera lösningarna på dessa delproblem är K.

Varje problemstorlek på n/2 är uppdelad i två delproblem vardera med storlek n/4 och så vidare.

På sista nivån kommer delproblemstorleken att minskas till 1. Med andra ord, vi träffade äntligen basfallet.

git rebase

Låt oss följa stegen för att lösa denna återkommande relation,

Steg 1: Rita rekursionsträdet

Steg 2: Beräkna höjden på trädet

Eftersom vi vet att när vi kontinuerligt dividerar ett tal med 2, kommer det en tid då detta tal reduceras till 1. Samma som med problemstorleken N, anta att efter K divisioner med 2 blir N lika med 1, vilket innebär, ( n / 2^k) = 1

Här är n / 2^k problemstorleken på den sista nivån och den är alltid lika med 1.

Nu kan vi enkelt beräkna värdet på k från uttrycket ovan genom att ta log() till båda sidor. Nedan är en tydligare härledning,

n = 2^k

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

Så höjden på trädet är stock (n) bas 2.

Steg 3: Beräkna kostnaden på varje nivå

• Kostnad på Nivå-0 = K, två delproblem slås samman.
• Kostnad på Nivå-1 = K + K = 2*K, två delproblem slås samman två gånger.
• Kostnad på nivå-2 = K + K + K + K = 4*K, två delproblem slås samman fyra gånger. och så vidare....

Steg 4: Beräkna antalet noder på varje nivå

Låt oss först bestämma antalet noder i den sista nivån. Från rekursionsträdet kan vi härleda detta

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

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

Steg 5: Summa kostnaden för alla nivåerna

linux byta namn på katalogen

• Den totala kostnaden kan skrivas som,
• Total kostnad = kostnad för alla nivåer utom sista nivån + kostnad för sista nivån
• Total kostnad = Kostnad för nivå-0 + Kostnad för nivå-1 + Kostnad för nivå-2 +.... + Kostnad för nivå-log(n) + Kostnad för sista nivån

Kostnaden för den sista nivån beräknas separat eftersom det är basfallet och ingen sammanslagning görs på den sista nivån, så kostnaden för att lösa ett enstaka problem på denna nivå är ett konstant värde. Låt oss ta det som O (1).

Låt oss lägga in värdena i formlerna,

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

Om du noggrant tittar på uttrycket ovan, bildar det en geometrisk progression (a, ar, ar^2, ar^3 ...... oändlig tid). Summan av GP ges av S(N) = a / (r - 1). Här är den första termen och r är det gemensamma förhållandet.