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 funktion** er en funktion, der kalder sig selv for at løse et problem ved at opdele det i mindre, enklere dele.



Definition

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 enklere tilfælde. Det bruges ofte til opgaver som behandling af træstrukturer, udforskning af stier eller opdeling af strukturer (f.eks. lister, strenge).



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å trin for trin for at forstå, hvordan dette fungerer:

1. `times = 3` → betingelsen er sand, udskriv besked, kald `print_message(message, 2)`;
2. `times = 2` → betingelsen er sand, udskriv besked, kald `print_message(message, 1)`;
3. `times = 1` → betingelsen er sand, udskriv besked, kald `print_message(message, 0)`;
4. `times = 0` → betingelsen er falsk, rekursionen stopper.

**Resultat**: beskeden udskrives tre gange.



## Kaldestakken

Hver gang funktionen kalder sig selv, tilføjes en ny ramme til **kaldestakken** — en hukommelsesstruktur, der holder styr på aktive funktionskald. Når basis-tilfældet nås, afsluttes hvert tidligere kald ét efter ét i omvendt rækkefølge.

Enhver rekursiv funktion skal have et basis-tilfælde. Uden dette vil funktionen kalde sig selv uendeligt og forårsage en `RecursionError`.

Bemærk

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 af, hvordan funktioner former Python-programmering. Opnå færdigheder i at definere og kalde funktioner, arbejde med argumenter, håndtere returværdier samt skabe fleksibel og effektiv kode ved hjælp af rekursion og lambda-udtryk.

Udforsk, hvad funktioner er, og hvorfor de er essentielle i Python. Lær, hvordan man opretter funktioner, definerer argumenter, håndterer returværdier og bruger indbyggede funktioner effektivt.

Lær hvordan positionelle og valgfrie argumenter fungerer i Python. Byg fleksible funktioner, der håndterer forskellige input og øger fleksibiliteten i din kode.

Forstå hvordan man arbejder med vilkårlige og navngivne argumenter for at håndtere variable inputstørrelser. Lær hvordan disse teknikker gør dine funktioner mere dynamiske og organiserede.

Opdag, hvordan returværdier repræsenterer en funktions output. Lær at returnere enkelt- eller flere værdier, bruge None og udforsk generatorer for mere avanceret styring af dataflow.

Lås op for avancerede funktionskoncepter med rekursion og lambda-funktioner. Lær, hvordan rekursion løser gentagne problemer, og hvordan lambda-udtryk skaber korte, énliniers funktioner.

Rekursion

Hvorfor bruge rekursion?

Et simpelt eksempel

Kaldestakken

Løsning