Lære Rekursion | Rekursion og Lambda-Funktioner

Definition

Rekursion er en programmeringsteknik, hvor en funktion kalder sig selv for at løse et problem i mindre dele. Det er særligt nyttigt til problemer med gentagende struktur eller naturlige delproblemer.

De vigtigste elementer i rekursion er:

Basis-tilfælde: betingelsen, der stopper rekursionen;
Rekursivt tilfælde: den del, hvor funktionen kalder sig selv med et simplere input.

Hvorfor bruge rekursion?

Nogle problemer kan naturligt udtrykkes som mindre delproblemer. Rekursion giver en klar og elegant måde at løse disse på ved at lade en funktion kalde sig selv for at håndtere de simplere tilfælde. Det bruges ofte til opgaver som behandling af træstrukturer, udforskning af stier eller opdeling af strukturer (f.eks. lister, strenge).


              1234567
            
def print_message(message, times):
    if times > 0:    # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)    # Recursive case

# Function call
print_message("Hello, Recursion!", 3)

Lad os gennemgå dette rekursive program trin for trin:

Betingelsestjek: hvis times > 0, fortsætter funktionen. I dette tilfælde er times = 3, så betingelsen er sand;
Udskriv besked: funktionen udskriver "Hello, Recursion!";
Rekursivt kald: funktionen kalder sig selv med times - 1;
Gentagelse: denne proces fortsætter, indtil times er lig med 0;
Afslutning: når betingelsen times > 0 ikke længere er sand, stopper rekursionen, og programmet afsluttes.

Resultat: Beskeden "Hello, Recursion!" udskrives tre gange.

Forståelse af forløbet:

Hver gang funktionen kalder sig selv, tilføjes en ny ramme til kaldestakken (en hukommelsesstruktur, der holder styr på aktive funktionskald). Funktionen bliver ved med at kalde sig selv med en mindre times-værdi. Når den når basis-tilfældet (times == 0), stopper den. Derefter afsluttes hvert tidligere kald én efter én i omvendt rækkefølge. Denne backtracking-adfærd er essentiel for, hvordan rekursion fungerer.

Opgave

Swipe to start coding

Givet en streng, der repræsenterer et telefonnummer, som kan indeholde mellemrum, bindestreger, parenteser eller andre ikke-numeriske tegn. Målet er at udtrække kun cifrene ved hjælp af rekursion.

Hvis inputstrengen number er tom, returneres en tom streng.
Kontroller om det første tegn i strengen number er et ciffer ved at bruge metoden isdigit() i en if-betingelse.
Hvis det er et ciffer, sammenkæd det med resultatet af et rekursivt kald til format_phone_number, hvor delstrengen fra og med det andet tegn sendes med.
Hvis det ikke er et ciffer, udfør et rekursivt kald til format_phone_number, hvor det første tegn springes over.

Løsning

Var alt klart?

Tak for dine kommentarer!

Sektion 5. Kapitel 1

single

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Suggested prompts:

Can you explain what happens if there is no base case in a recursive function?

What are some common mistakes to avoid when using recursion?

Can you show another example of recursion in Python?

Awesome!

Completion rate improved to 4.35

Stryg for at vise menuen