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

**再帰関数**は、問題をより小さく単純な部分に分割して解決するために自分自身を呼び出す関数。 



定義

再帰の主な要素：
- **基本ケース**：再帰を停止する条件；
- **再帰ケース**：関数がより単純な入力で自分自身を呼び出す部分。

## なぜ再帰を使うのか？

一部の問題は、より小さな部分問題として自然に表現できる。再帰は、関数が自分自身を呼び出して単純なケースを処理することで、これらを簡潔かつエレガントに解決する方法を提供する。木構造の処理、経路の探索、構造（例：リストや文字列）の分解などでよく使用される。



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)

この動作を理解するために、ステップごとに見ていきます:

1. `times = 3` → 条件が真、メッセージを出力、`print_message(message, 2)` を呼び出す；
2. `times = 2` → 条件が真、メッセージを出力、`print_message(message, 1)` を呼び出す；
3. `times = 1` → 条件が真、メッセージを出力、`print_message(message, 0)` を呼び出す；
4. `times = 0` → 条件が偽、再帰が停止。

**結果**: メッセージが3回出力される。



## コールスタック

関数が自分自身を呼び出すたびに、新しいフレームが**コールスタック**（アクティブな関数呼び出しを管理するメモリ構造）に追加されます。ベースケースに到達すると、それまでの呼び出しが逆順で一つずつ完了します。

すべての再帰関数にはベースケースが必要です。ベースケースがない場合、関数は永遠に自分自身を呼び出し続け、`RecursionError`が発生します。

注意

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

関数がPythonプログラミングにどのような影響を与えるかについての確かな理解を身につけます。関数の定義と呼び出し、引数の操作、戻り値の処理、再帰やラムダ式を用いた柔軟で効率的なコードの作成を習得します。

関数とは何か、そしてなぜPythonで重要なのかを探ります。関数の作成方法、引数の定義、戻り値の処理、組み込み関数の効果的な使用方法について学びます。

Pythonにおける位置引数とオプション引数の仕組みを学習します。さまざまな入力に対応できる柔軟な関数を作成し、コードの柔軟性を向上させます。

可変長引数およびキーワード引数を使用して、入力サイズが異なる場合の処理方法を理解します。これらの手法によって、関数がより動的かつ整理されたものになることを学びます。

戻り値が関数の出力をどのように表すかを学びます。単一または複数の値の返却、Noneの使用、より高度なデータフロー制御のためのジェネレーターの活用について解説します。

再帰とラムダ関数による高度な関数の概念を習得します。再帰が繰り返しの問題をどのように解決するか、ラムダ式が簡潔な1行関数をどのように作成するかを学びます。

再帰

なぜ再帰を使うのか？

シンプルな例

コールスタック

解答