Summary
Recursion is a technique where a function defines a base case to stop and a recursive case that calls itself with simpler input to solve problems.

General domain of usage
processing trees

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



Määritelmä

Rekursiivisen ratkaisun keskeiset osat:
- **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 kautta. Rekursio tarjoaa selkeän ja elegantin tavan ratkaista nämä, kun funktio kutsuu itseään käsittelemään yksinkertaisempia tapauksia. Sitä 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, tulostetaan viesti, kutsutaan `print_message(message, 2)`;
2. `times = 2` → ehto on tosi, tulostetaan viesti, kutsutaan `print_message(message, 1)`;
3. `times = 1` → ehto on tosi, tulostetaan viesti, 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

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

Tutustu siihen, mitä funktiot ovat ja miksi ne ovat olennaisia Pythonissa. Opiskele funktioiden luomista, argumenttien määrittelyä, palautusarvojen käsittelyä sekä sisäänrakennettujen funktioiden tehokasta käyttöä.

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

Ymmärrä, miten käsitellä mielivaltaisia ja avainsana-argumentteja vaihtelevien syötekokojen hallitsemiseksi. Opi, miten nämä tekniikat tekevät funktioista dynaamisempia ja järjestelmällisempiä.

Opi, miten palautusarvot 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, miten rekursio ratkaisee toistuvia ongelmia ja miten lambda-lausekkeilla luodaan tiiviitä, yhdellä rivillä määriteltyjä funktioita.

Rekurssio

Miksi käyttää rekursiota?

Yksinkertainen esimerkki

Kutsupino

Ratkaisu