Forberedelse til kodeintervjuer · leksjon

Rekursjonsrammeverk: basistilfelle, tillit, bygg

Bruk tretrinnsmetoden til å skrive korrekte rekursive løsninger for fakultet, potens og siffersum uten å følge hvert eneste kall.

Leksjon 1 av 413 trinn

Rekursjonsrammeverk: basistilfelle, tillit, bygg er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hvorfor rekursjon føles vanskelig

De fleste nybegynnere prøver å følge med på hvert rekursive kall mentalt, noe som raskt blir overveldende selv ved rekursjon med bare fem nivåer. Den profesjonelle tilnærmingen er å bruke et rammeverk i tre trinn — Basistilfelle, tillit, oppbygging — som lar Dem skrive korrekte rekursive funksjoner uten å simulere hele kalltreet mentalt.

Rammeverket omtales noen ganger som leap of faith: De stoler på at funksjonen fungerer for mindre inndata, og bruker denne antakelsen til å bygge løsningen for større inndata.

Trinn 1: Definer basistilfellet

Et basistilfelle er det enkleste inputet der svaret er kjent uten mer rekursjon. Enhver rekursiv funksjon må ha minst ett basistilfelle; uten det vil funksjonen rekursere for alltid (stakkoverflyt). Gode basistilfeller er: tom liste, liste med ett element, n == 0, n == 1 eller at problemet reduseres til en triviell identitet.

Skriv basistilfellet først, før den rekursive logikken. Finn det ved å spørre: 'Hva er den minste versjonen av dette problemet som jeg kan besvare umiddelbart?'

# Base cases for common problems
def factorial(n):
    if n == 0:          # base case: 0! = 1
        return 1
    # ... recursive step below

def sum_list(lst):
    if not lst:         # base case: sum of empty list is 0
        return 0
    # ...

def height(node):
    if node is None:    # base case: height of null node is 0
        return 0
    # ...

print('Base cases identified')

Trinn 2: Stol på det rekursive kallet

Tillitssteget er et sprang i troen: Anta at funksjonen allerede fungerer korrekt for alle input som er strengt mindre enn det gjeldende. De trenger ikke å bevise dette for hvert mindre input akkurat nå – induksjonsbeviset garanterer det. Kall ganske enkelt funksjonen på det mindre delproblemet, og stol på at den returnerer riktig resultat.

Dette er steget nybegynnere hopper over fordi de i stedet prøver å simulere alt mentalt. Motstå den trangen; når De først har gjort rammeverket til en del av tankegangen, fungerer det også ved vilkårlig dyp rekursjon.

# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11  (we TRUST this, don't trace it)
# Build: 3 + 11 = 14

# So:
def sum_list(lst):
    if not lst:
        return 0
    # Trust that sum_list(lst[1:]) returns sum of the rest
    return lst[0] + sum_list(lst[1:])

print(sum_list([3, 1, 4, 1, 5]))  # 14

Trinn 3: Bygg løsningen

Byggesteget kombinerer resultatet fra det pålitelige delproblemet med bidraget fra det gjeldende elementet for å produsere svaret for hele inputet. Dette er vanligvis én enkelt linje: Utfør en operasjon på det gjeldende elementet og resultatet fra det rekursive kallet. Vanlige byggesteg er å legge til en sum, sette et element først i en liste, øke en teller eller kombinere to delresultater.

def factorial(n):
    if n == 0:
        return 1
    # Trust: factorial(n-1) gives (n-1)!
    # Build: n * (n-1)! = n!
    return n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    # Trust: power(base, exp-1) gives base^(exp-1)
    # Build: base * base^(exp-1) = base^exp
    return base * power(base, exp - 1)

print(factorial(6))    # 720
print(power(2, 10))    # 1024

Bruk av rammeverket på siffersummen

Problem: Beregn siffersummen til et ikke-negativt heltall. Basistilfelle: n == 0 → summen er 0 (eller n < 10 → n selv). Tillit: sumDigits(n // 10) returnerer summen av alle sifrene unntatt det siste. Bygg: Legg det siste sifferet n % 10 til det pålitelige resultatet. Rammeverket gir løsningen i tre deklarative trinn.

def sumDigits(n):
    if n < 10:
        return n            # base case: single digit
    # Trust: sumDigits(n // 10) gives sum of all digits except last
    # Build: add the last digit
    return n % 10 + sumDigits(n // 10)

print(sumDigits(0))      # 0
print(sumDigits(7))      # 7
print(sumDigits(123))    # 6
print(sumDigits(9999))   # 36

Fibonacci: To delproblemer

Fibonacci krever to rekursive kall: fib(n-1) og fib(n-2). Bruk rammeverket: Basistilfellene er fib(0) = 0 og fib(1) = 1. Tillit: Begge de mindre kallene returnerer de riktige Fibonacci-verdiene. Bygg: Returner summen av dem. Denne naive implementasjonen har tidskompleksitet O(2^n) – det løser vi i leksjonen om memoisering.

def fib(n):
    if n <= 1:
        return n      # base cases: fib(0)=0, fib(1)=1
    # Trust both smaller sub-problems
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f'fib({i}) = {fib(i)}')  # 0,1,1,2,3,5,8,13

Reverser en streng rekursivt

Problem: Reverser en streng rekursivt. Basistilfelle: tom streng eller ett enkelt tegn – den er allerede reversert. Tillit: reverse(s[1:]) returnerer reverseringen av alt etter det første tegnet. Bygg: Legg det første tegnet til på slutten av den reverserte resten. Rammeverket gir en løsning på tre linjer.

def reverse_str(s):
    if len(s) <= 1:
        return s            # base case
    # Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
    # Build: append first character at end
    return reverse_str(s[1:]) + s[0]

print(reverse_str(''))        # ''
print(reverse_str('a'))       # 'a'
print(reverse_str('hello'))   # 'olleh'
print(reverse_str('racecar')) # 'racecar'

Tell forekomster rekursivt

Problem: Tell hvor mange ganger en målverdi forekommer i en liste, rekursivt. Basistilfelle: tom liste – antallet er 0. Tillit: count(lst[1:], target) returnerer antallet i resten av listen. Bygg: Legg til 1 hvis det første elementet samsvarer med målverdien, ellers legg til 0. Hvert rekursive trinn nærmer seg basistilfellet ved å redusere listestørrelsen med 1.

def count_occurrences(lst, target):
    if not lst:
        return 0
    # Trust: count in rest of list is handled recursively
    # Build: add 1 if first element matches, else 0
    return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)

print(count_occurrences([1, 2, 3, 2, 4, 2], 2))  # 3
print(count_occurrences([], 5))                    # 0
print(count_occurrences([7, 7, 7], 7))             # 3

Sjekk om en liste er sortert

Problem: Sjekk rekursivt om en liste er sortert i stigende rekkefølge. Basistilfelle: En liste med 0 eller 1 element er alltid sortert. Tillit: is_sorted(lst[1:]) forteller om resten av listen er sortert. Bygg: Listen er sortert hvis det første elementet er <= det andre OG resten av listen er sortert. Dette er et tydelig eksempel der byggesteget bruker et logisk AND av to betingelser.

def is_sorted(lst):
    if len(lst) <= 1:
        return True
    # Trust: is_sorted(lst[1:]) tells us if tail is sorted
    # Build: head <= second element AND tail is sorted
    return lst[0] <= lst[1] and is_sorted(lst[1:])

print(is_sorted([]))           # True
print(is_sorted([1]))          # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False

Binærsøk rekursivt (repetisjon)

Binærsøk uttrykt rekursivt ved hjelp av rammeverket: Basistilfelle: lo > hi → ikke funnet (returner -1). Tillit: Det rekursive kallet på riktig halvdel finner målverdien eller returnerer -1. Bygg: Beregn midtpunktet, sammenlign og kall på riktig halvdel. Den rekursive formen viser tydelig del-og-hersk-strukturen, selv om den iterative formen foretrekkes i produksjon på grunn av O(1)-plass.

def binary_search(arr, target, lo, hi):
    if lo > hi:          # base case: search space exhausted
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    # Trust both halves return correct results
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))   # 3
print(binary_search(arr, 4, 0, len(arr) - 1))   # -1

Når bør De bruke rekursjon fremfor iterasjon

Rekursjon egner seg særlig godt når problemet naturlig kan deles opp i mindre delproblemer av samme type (trær, del-og-hersk og tilbakesporing). Iterasjon foretrekkes når: rekursjonsdybden er stor (noe som kan føre til stakkoverflyt i Python, der standardgrensen er omtrent 1000), de rekursive og iterative versjonene er like tydelige, eller problemet er en enkel løkke (fakultet, Fibonacci uten memoisering).

En god tommelfingerregel er: Hvis det føles naturlig å tegne et rekursjonstre, bør De bruke rekursjon. Hvis treet er en rett linje (halerekursjon), bør De konvertere til iterasjon.

import sys

# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit())  # 1000

# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
    total = 0
    for x in lst:
        total += x
    return total

big = list(range(2000))
print(sum_list_iter(big))  # 1999000 — no stack overflow

Kunnskapssjekk

Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: at rammeverket i tre trinn består av Basistilfelle (det enkleste kjente svaret), Tillit (anta at delproblemet er løst) og Bygg (kombiner det gjeldende elementet med det pålitelige resultatet), å skrive basistilfeller først og unngå å spore hele kalltrær mentalt, og å bruke iterasjon når rekursjonsdybden medfører risiko for stakkoverflyt, eller når de rekursive og iterative formene er like tydelige. Neste gang visualiserer vi kallestakken i detalj.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Rekursjonsrammeverk: basistilfelle, tillit, bygg» gratis?

Ja – hele teksten i «Rekursjonsrammeverk: basistilfelle, tillit, bygg» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Rekursjonsrammeverk: basistilfelle, tillit, bygg»?

Bruk tretrinnsmetoden til å skrive korrekte rekursive løsninger for fakultet, potens og siffersum uten å følge hvert eneste kall. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Rekursjonsrammeverk: basistilfelle, tillit, bygg»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

Rekursjonsrammeverk: basistilfelle, tillit, bygg
Visualisering av kallstakken
Avveininger mellom rekursiv og iterativ løsning
Memoisation: hurtigbufring av rekursive resultater

← Tilbake til Forberedelse til kodeintervjuer