再帰の概念

1.1 再帰の定義と基本的なコンセプト。

再帰って、自分自身を繰り返すことだよ。説明書があって、その一部にその説明書に従えって書いてあるみたいなもんだね。例えば、自分に"その命令を繰り返せ"って言ったような感じ。

現実の例:

向かい合った鏡:

二つの鏡の間に立っていると想像してみて。自分の反射を見て、その反射の中にも自分の反射があって、それがずっと続く。これは再帰の例だね。どの鏡も他の鏡の反射を見せているから。

マトリョーシカ:

マトリョーシカは中にさらに別の人形があって、その中にもまた別の人形がある、って続く。最小の人形にたどり着くと、それ以上開けるものがないよね。これが再帰の 基本ケースみたいなもので、止まるべき瞬間 だね。

ピザの分け方:

ピザを半分に分けると想像してみて。それから半分を取ってさらに半分に分ける。それを繰り返して、分けるのが難しいくらい小さくなるまで続ける。パーツに分けるのは再帰的なプロセスで、これ以上分けられない瞬間が基本ケースだね。

大事！ 再帰って、同じ命令を無限に繰り返すって話じゃなくて、むしろ難しい問題をパーツに分けるとき、そのパーツの解決方法が全体の問題の解決方法に似ているって話だよ。

どうやって動くの？

再帰を理解するには2つの基本的な概念を知っておく必要があるよ:

• 基本ケース: これは再帰が終わる条件だよ。例えば、マトリョーシカの例では、一番小さなマトリョーシカを開けて中に何もない時が基本ケース。
• 再帰ケース: これは、より小さなパーツで問題を繰り返す時だよ。ピザの例では、一片を分ける、そしてその半分を分ける、と続く。

なぜ便利なの？

再帰は複雑な問題をシンプルなパーツに分けることで解決するのに役立つよ。問題を一度に全部解く代わりに、小さなパーツごとに解決する感じ。

他の生活の例:

物語の中の物語:

物語の主人公が別の物語を話し始めて、その物語の主人公がさらに別の物語を話し始めるところを想像してみて。一つの物語が終わると、前の物語に戻る。最後の物語が終わると基本ケースだね。

再帰的な絵画:

大きな三角形を描いて、その三角形の各角に小さな三角形を描く。それを続けて、三角形が小さすぎて描けなくなるまで続ける。基本ケースは、三角形が小さすぎて描けなくなった時だね。

1.2 基本ケース：定義と例

基本ケースは、再帰呼び出しを終了させて、特定の値を返すようにする条件だよ。通常、これは一番シンプルで明白な問題の解決策で、さらなる再帰を必要としないものだね。

基本ケースの例:

数の階乗:

数nの階乗はF(n) == 1*2*3*…*nと表される。同様に、F(n) == n* F(n-1)でもあるよ。

基本ケース: 数0または1の階乗は1. F(0) == F(1)==1だよ。

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本ケース
    else:
        return n * factorial(n - 1)
        

フィボナッチ数:

フィボナッチ数は次のような数列だよ: 1, 1, 2, 3, 5, 8, 13, … 各次の数は2つ前の数の和なの。F(n) == F(n-1) + F(n-2)

基本ケース: 最初の2つのフィボナッチ数は1だから、「ゼロ番目」のフィボナッチ数は0だよ。つまりF(0) = 0 と F(1) = 1。

def fibonacci(n):
    if n == 0:
        return 0  # 基本ケース
    elif n == 1:
        return 1  # 基本ケース
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 再帰ケース：定義と例

再帰ケースは、新しいパラメータで自分自身を呼び出すことで問題を解決する部分だよ。新しいパラメータは基本ケースに近づけるためのもので、各再帰呼び出しは問題を縮小したり変更したりして、最終的に基本ケースに達する。

再帰ケースの例:

数の階乗:

再帰ケース: 数nの階乗はnを数n-1の階乗で掛けたものだよ。

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本ケース
    else:
        return n * factorial(n - 1)  # 再帰ケース
        

フィボナッチ数:

再帰ケース: F(n)はF(n-1)とF(n-2)の和だよ。

def fibonacci(n):
    if n == 0:
        return 0  # 基本ケース
    elif n == 1:
        return 1  # 基本ケース
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 再帰ケース
        

1.4 再帰アルゴリズムの例

1. バイナリツリーのトラバース:

"in-order"順序でのトラバースの例。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# 使用例:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. リスト内の最大要素の検索:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # 基本ケース
    else:
        max_of_rest = find_max(lst[1:])  # 再帰ケース
        return max(lst[0], max_of_rest)
        
# 使用例:
print(find_max([1, 5, 3, 9, 2]))  # 出力: 9
        
        

3. 再帰的バイナリサーチ:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 基本ケース: 要素が見つからない
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 基本ケース: 要素が見つかった
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 再帰ケース
    else:
        return binary_search(arr, target, left, mid - 1)  # 再帰ケース 
# 使用例:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # 出力: 4