Rekursion

Question 1

Vad ändras i version 2 av “Hello World” för att undvika oändlig rekursion?

Answer 1

I version 2 läggs ett termineringsvillkor till som stoppar rekursionen när n blir 0, vilket gör att funktionen slutar anropa sig själv efter ett visst antal gånger. “Hello World” skrivs ut fyra gånger (från 4 till 1) innan funktionen avslutas, vilket visar att rekursionen nu har ett korrekt termineringsvillkor.

Question 2

Vad är rekursion?

Answer 2

Rekursion är en teknik där en funktion anropar sig själv för att lösa ett problem. Den bygger på principen “divide and conquer” där ett stort problem bryts ner i mindre delar som är enklare att lösa.

Question 3

Vad är ett termineringsvillkor i rekursion?

Answer 3

Ett termineringsvillkor är ett tillstånd där den rekursiva funktionen slutar att anropa sig själv. Detta är nödvändigt för att undvika oändliga loopar och säkerställa att funktionen avslutas korrekt.

Question 4

Vad händer i rekursiv “Hello World” (version 1)?

Answer 4

Funktionen write_string anropar sig själv utan ett termineringsvillkor, vilket resulterar i ett oändligt antal anrop tills Python kastar ett felmeddelande om att maxdjupet för rekursion har överskridits. Resultatet är att “Hello World” skrivs ut ett stort antal gånger (995 gånger) innan programmet kraschar med ett felmeddelande på grund av för många rekursiva anrop.

Question 5

Hur fungerar version 3 av “Hello World” rekursivt?

Answer 5

I version 3 anropas funktionen write_string först rekursivt innan utskriften sker, vilket resulterar i att “Hello World” skrivs ut i omvänd ordning (från 1 till 4). “Hello World” skrivs ut i omvänd ordning, från 1 till 4, vilket visar effekten av att skriva ut meddelandet efter det rekursiva anropet.

Question 6

Vad gör funktionen fact(n) i exemplet med rekursion?

Answer 6

Funktionen fact(n) beräknar fakulteten av n genom att anropa sig själv rekursivt. Om n är större än eller lika med 1, multiplicerar den n med fact(n-1) tills den når 1. Om n är 0 eller 1, returnerar den 1 direkt.

Question 7

Vad är termineringsvillkoret i fact(n)-funktionen?

Answer 7

Termineringsvillkoret är när n är 0 eller 1. I det fallet returnerar funktionen 1 och stoppar den rekursiva anropningen.

Question 8

Vad är resultatet av att köra fact(5)?

Answer 8

Resultatet är 120 eftersom 5! = 5 × 4 × 3 × 2 × 1 = 120.

Question 9

Hur fungerar den rekursiva funktionen för att skriva ut en sträng baklänges?

Answer 9

Funktionen writeRecursive(s, n) anropar sig själv för att flytta till slutet av strängen och skriver sedan ut varje tecken på vägen tillbaka genom anropen, vilket gör att strängen skrivs ut baklänges.

Question 10

Vad blir resultatet av att köra writeRecursive(“Hello”, 0)?

Answer 10

Resultatet är att “Hello” skrivs ut baklänges som “olleH”.

Question 10

Vad är termineringsvillkoret i writeRecursive(s, n)?

Answer 10

Termineringsvillkoret är när n är lika med längden på strängen. Då slutar funktionen att anropa sig själv.

Question 11

Hur fungerar den rekursiva funktionen för att hitta alla delsträngar?

Answer 11

Funktionen find_all(substr, s) letar efter en delsträng i en sträng, och om den hittar en match, anropar den sig själv med resten av strängen. Varje gång den hittar en match, returnerar den 1 och lägger till det rekursiva resultatet.

Question 12

Vad är termineringsvillkoret i find_all(substr, s)?

Answer 12

Termineringsvillkoret är när delsträngen inte längre finns i strängen (dvs. result == -1). Då returnerar funktionen 0.

Question 14

Vad är resultatet av att köra find_all(‘doo’, ‘doo bee doo bee doo’)?

Answer 14

Resultatet är 3 eftersom “doo” förekommer tre gånger i strängen “doo bee doo bee doo”.