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

**Rekursiivinen funktio** on funktio, joka kutsuu itseään ratkaistakseen ongelman jakamalla sen pienempiin, yksinkertaisempiin osiin.



Määritelmä

Rekursiivisen ratkaisun keskeiset osat ovat:
- **Perustapaus**: ehto, joka pysäyttää rekursion;
- **Rekursiotapaus**: kohta, jossa funktio kutsuu itseään yksinkertaisemmalla syötteellä.

## Miksi käyttää rekursiota?

Jotkin ongelmat voidaan luontevasti ilmaista pienempien osatehtävien avulla. Rekursio tarjoaa selkeän ja elegantin tavan ratkaista nämä antamalla funktion kutsua itseään käsittelemään yksinkertaisempia tapauksia. Rekursiota käytetään yleisesti esimerkiksi puiden käsittelyssä, polkujen tutkimisessa tai rakenteiden (esim. listat, merkkijonot) pilkkomisessa.



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)

Käy vaihe vaiheelta läpi, miten tämä toimii:

1. `times = 3` → ehto on tosi, viesti tulostetaan, kutsutaan `print_message(message, 2)`;
2. `times = 2` → ehto on tosi, viesti tulostetaan, kutsutaan `print_message(message, 1)`;
3. `times = 1` → ehto on tosi, viesti tulostetaan, kutsutaan `print_message(message, 0)`;
4. `times = 0` → ehto on epätosi, rekursio päättyy.

**Tulos**: viesti tulostetaan kolme kertaa.



## Kutsupino

Joka kerta kun funktio kutsuu itseään, se lisää uuden kehyksen **kutsupinoon** — muistirakenteeseen, joka seuraa aktiivisia funktiokutsuja. Kun pohjatapaus saavutetaan, jokainen aiempi kutsu suoritetaan loppuun yksi kerrallaan käänteisessä järjestyksessä.

Jokaisella rekursiivisella funktiolla täytyy olla pohjatapaus. Ilman sitä funktio kutsuu itseään loputtomasti ja aiheuttaa `RecursionError`-virheen.

Huomio

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

Saavuta vankka ymmärrys siitä, miten funktiot muovaavat Python-ohjelmointia. Hallitse funktioiden määrittely ja kutsuminen, argumenttien käsittely, palautusarvojen hallinta sekä joustavan ja tehokkaan koodin luominen rekursion ja lambda-lausekkeiden avulla.

Tutustu siihen, mitä funktiot ovat ja miksi ne ovat olennaisia Pythonissa. Opiskele, kuinka funktioita luodaan, määritellään argumentteja, käsitellään paluuarvoja ja käytetään sisäänrakennettuja funktioita tehokkaasti.

Opi, miten positionaaliset ja valinnaiset argumentit toimivat Pythonissa. Rakenna mukautuvia funktioita, jotka käsittelevät erilaisia syötteitä ja parantavat koodisi joustavuutta.

Ymmärrä, kuinka käsitellä mielivaltaisia ja avainsana-argumentteja vaihtelevan syötteen hallitsemiseksi. Opi, miten nämä tekniikat tekevät funktioistasi dynaamisempia ja järjestelmällisempiä.

Opi, miten paluuarvot edustavat funktion tuotosarvoa. Palauta yksi tai useampi arvo, käytä None-arvoa ja tutustu generaattoreihin edistyneemmän tietovirran hallinnan saavuttamiseksi.

Avaa edistyneet funktiokäsitteet rekursion ja lambda-funktioiden avulla. Opiskele, kuinka rekursio ratkaisee toistuvia ongelmia ja kuinka lambda-lausekkeilla luodaan tiiviitä, yhdellä rivillä kirjoitettuja funktioita.

Rekurssio

Miksi käyttää rekursiota?

Yksinkertainen esimerkki

Kutsupino

Ratkaisu