Tänk rekursivt: basfall och rekursion
Dela upp ett problem i mindre kopior
Tänk rekursivt: basfall och rekursion är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad rekursion innebär
Rekursion är en funktion som löser ett problem genom att anropa sig själv med en mindre del, tills delen är tillräckligt liten för att besvaras direkt. 🌀
Lita på det mindre delproblemet
Den viktiga tanken är tillitssteget: anta att det rekursiva anropet redan fungerar för den mindre indatan och bygg sedan er lösning ovanpå det.
Varje rekursion behöver ett basfall
Basfallet är den minsta indata som besvaras utan rekursion. Utan det anropar funktionen sig själv för evigt och kraschar.
Rekursionsfallet
Rekursionsfallet minskar problemet och anropar funktionen med den mindre versionen. Varje anrop måste föra er närmare basfallet.
Fakultet som första exempel
Här visar fakultet båda delarna: ett basfall vid noll och ett rekursivt anrop med n minus ett.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Så fungerar anropsstacken
Varje anrop väntar på anropsstacken tills det inre anropet returnerar. Det djupaste anropet avslutas först, sedan nystas svaren tillbaka uppåt.
Håll koll på rekursionsdjupet
Python begränsar rekursionsdjupet till omkring 1000 som standard. Djup rekursion i tävlingsprogrammering kräver sys.setrecursionlimit för att undvika ett körtidsfel.
import sys
sys.setrecursionlimit(300000)Gör framsteg vid varje anrop
En korrekt rekursion minskar alltid indata mot basfallet. Om den någon gång når samma storlek igen loopar den för evigt. ⚠️
Summera en lista rekursivt
Den här rekursiva summan tar bort det första elementet och litar sedan på anropet för att lägga till resten av listan.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Rekursionsträd visar förgreningar
När en funktion gör mer än ett anrop bildar arbetet ett rekursionsträd. Storleken anger den totala kostnaden.
Upprepat arbete kan vara långsamt
Naiv Fibonacci räknar om samma värden om och om igen, vilket ger exponentiell tidskomplexitet. Memoisering av svaren löser problemet omedelbart.
Snabb kontroll
Vad händer om en rekursiv funktion saknar basfall?
Repetition: två delar, en idé
Du har lärt dig att rekursion behöver ett basfall för att stoppa och ett rekursivt fall som minskar indata. Förlita dig på det mindre anropet, så följer resten. 🎯
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Tänk rekursivt: basfall och rekursion” gratis?
Ja – hela texten till ”Tänk rekursivt: basfall och rekursion” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Tänk rekursivt: basfall och rekursion”?
Dela upp ett problem i mindre kopior Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Tänk rekursivt: basfall och rekursion”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Tänk rekursivt: basfall och rekursion
- Generera alla delmängder
- Permutationer och idén bakom N-damer
- Beskär sökningen för att klara tidsgränsen