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** är en funktion som anropar sig själv för att lösa ett problem genom att dela upp det i mindre, enklare delar.



Definition

De viktigaste delarna av rekursion är:
- **Basfall**: villkoret som stoppar rekursionen;
- **Rekursivt fall**: delen där funktionen anropar sig själv med ett enklare argument.

## Varför använda rekursion?

Vissa problem kan naturligt uttryckas i form av mindre delproblem. Rekursion ger ett tydligt och elegant sätt att lösa dessa genom att låta en funktion anropa sig själv för att hantera de enklare fallen. Det används ofta vid uppgifter som att bearbeta trädstrukturer, utforska vägar eller dela upp strukturer (t.ex. listor, strängar).



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å igenom steg för steg för att förstå hur detta fungerar:

1. `times = 3` → villkoret är sant, skriv ut meddelandet, anropa `print_message(message, 2)`;
2. `times = 2` → villkoret är sant, skriv ut meddelandet, anropa `print_message(message, 1)`;
3. `times = 1` → villkoret är sant, skriv ut meddelandet, anropa `print_message(message, 0)`;
4. `times = 0` → villkoret är falskt, rekursionen stoppas.

**Resultat**: meddelandet skrivs ut tre gånger.



## Anropsstacken

Varje gång funktionen anropar sig själv läggs en ny ram till **anropsstacken** — en minnesstruktur som håller reda på aktiva funktionsanrop. När basfallet nås avslutas varje tidigare anrop ett efter ett i omvänd ordning.

Varje rekursiv funktion måste ha ett basfall. Utan det kommer funktionen att anropa sig själv oändligt och orsaka ett `RecursionError`.

Notera

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 gedigen förståelse för hur funktioner formar Python-programmering. Bemästra att definiera och anropa funktioner, arbeta med argument, hantera returvärden och skapa flexibel, effektiv kod med rekursion och lambda-uttryck.

Utforska vad funktioner är och varför de är viktiga i Python. Lär dig hur man skapar funktioner, definierar argument, hanterar returvärden och använder inbyggda funktioner effektivt.

Lär dig hur positionella och valfria argument fungerar i Python. Skapa anpassningsbara funktioner som hanterar olika indata och förbättrar flexibiliteten i din kod.

Förstå hur man arbetar med godtyckliga och nyckelordsargument för att hantera variabla inmatningsstorlekar. Lär dig hur dessa tekniker gör dina funktioner mer dynamiska och organiserade.

Upptäck hur returvärden representerar en funktions utdata. Lär dig att returnera enskilda eller flera värden, använda None och utforska generatorer för mer avancerad kontroll av dataflöde.

Lås upp avancerade funktionskoncept med rekursion och lambda-funktioner. Lär dig hur rekursion löser repetitiva problem och hur lambda-uttryck skapar koncisa, enradiga funktioner.

Rekursion

Varför använda rekursion?

Ett enkelt exempel

Anropsstacken

Lösning