Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

En **rekursiv funksjon** er en funksjon som kaller seg selv for å løse et problem ved å dele det opp i mindre, enklere deler.



Definisjon

De viktigste elementene i rekursjon er:
- **Basis-tilfelle**: betingelsen som stopper rekursjonen;
- **Rekursivt tilfelle**: delen der funksjonen kaller seg selv med et enklere input.

## Hvorfor bruke rekursjon?

Noen problemer kan naturlig uttrykkes som mindre delproblemer. Rekursjon gir en ryddig og elegant måte å løse disse på ved at en funksjon kaller seg selv for å håndtere de enklere tilfellene. Det brukes ofte til oppgaver som å prosessere trær, utforske stier eller dele opp strukturer (f.eks. lister, strenger).



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

print_message("Hello, Recursion!", 3)

Gå gjennom stegene for å forstå hvordan dette fungerer:

1. `times = 3` → betingelsen er sann, skriver ut melding, kaller `print_message(message, 2)`;
2. `times = 2` → betingelsen er sann, skriver ut melding, kaller `print_message(message, 1)`;
3. `times = 1` → betingelsen er sann, skriver ut melding, kaller `print_message(message, 0)`;
4. `times = 0` → betingelsen er usann, rekursjonen stopper.

**Resultat**: meldingen skrives ut tre ganger.



## Kallstakken

Hver gang funksjonen kaller seg selv, legges en ny ramme til **kallstakken** — en minnestruktur som holder oversikt over aktive funksjonskall. Når basis-tilfellet er nådd, fullføres hvert tidligere kall ett etter ett i motsatt rekkefølge.

Alle rekursive funksjoner må ha et basis-tilfelle. Uten dette vil funksjonen kalle seg selv uendelig og føre til en `RecursionError`.

Merk

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Få en solid forståelse av hvordan funksjoner former Python-programmering. Bli ekspert på å definere og kalle funksjoner, arbeide med argumenter, håndtere returverdier og lage fleksibel, effektiv kode ved bruk av rekursjon og lambda-uttrykk.

Utforsk hva funksjoner er og hvorfor de er essensielle i Python. Lær hvordan du oppretter funksjoner, definerer argumenter, håndterer returverdier og bruker innebygde funksjoner effektivt.

Lær hvordan posisjonelle og valgfrie argumenter fungerer i Python. Bygg tilpasningsdyktige funksjoner som håndterer ulike input og gir økt fleksibilitet i koden din.

Forstå hvordan du arbeider med vilkårlige og navngitte argumenter for å håndtere variable mengder input. Lær hvordan disse teknikkene gjør funksjonene dine mer dynamiske og organiserte.

Oppdag hvordan returverdier representerer en funksjons output. Lær å returnere én eller flere verdier, bruke None, og utforsk generatorer for mer avansert kontroll over datastrøm.

Lås opp avanserte funksjonskonsepter med rekursjon og lambda-funksjoner. Lær hvordan rekursjon løser repeterende problemer og hvordan lambda-uttrykk skaper konsise, énlinjers funksjoner.

Rekursjon

Hvorfor bruke rekursjon?

Et enkelt eksempel

Kallstakken

Løsning