前半：Pythonで「アルゴリズム」と「再帰関数」の土台をつくる
Pythonは文法がシンプルで、エラーも読みやすいので、アルゴリズムや再帰を学ぶにはかなり向いている言語だと思う。
ここではまず、「アルゴリズムってそもそも何？」「再帰関数って何者？」というところから、Pythonコードを交えながらじっくり土台を固めていく。
アルゴリズムとは何か
アルゴリズムを日常の言葉にすると
アルゴリズムは、一言でいうと「問題を解くための手順書」だ。
もっとくだけた言い方をすると、「こうやって進めれば必ずゴールにたどり着けるステップの並び」と言っていい。
たとえば「目玉焼きを作るアルゴリズム」を書くなら、こんな感じになる。
フライパンを火にかける
油をひく
卵を割り入れる
好みの固さになるまで焼く
皿に盛る
これをコンピュータが実行できる形にしたものが、プログラムとしてのアルゴリズムだ。
Pythonでコードを書くというのは、「コンピュータ用の手順書を書く」ことそのものだと思っていい。
なぜアルゴリズムがそんなに大事なのか
文法だけ知っていても、「とりあえず動くコード」は書ける。
でも、現実の世界ではそれだけでは足りない。
時間がかかりすぎて実用にならないコード
メモリを食いすぎて落ちるコード
入力次第で止まらなくなる危険なコード
こういうものは、文法的には正しくても「ダメなコード」だ。
アルゴリズムを学ぶというのは、「正しく・速く・安全に」問題を解くための考え方を鍛えることだと思ってほしい。
セキュリティの視点でも、アルゴリズムが弱いとDoS（サービス妨害）みたいな脆弱性を自分で仕込んでしまうことになる。
再帰関数とは何か（Python版）
一言でいうと「自分自身を呼び出す関数」
再帰関数（recursive function）は、「自分の中で自分自身を呼び出す関数」のことだ。
def foo(n):
# 何か処理
foo(n - 1) # 自分自身を呼んでいる
このままだと、永遠に foo が呼ばれ続けてしまう。
だから再帰には必ず「ここで終わる」という条件が必要になる。
再帰の2本柱：ベースケースと再帰ステップ
再帰関数には、必ず次の2つがセットで存在する。
ベースケース（基底条件・終わりの条件）
再帰ステップ（問題を少し小さくして自分を呼ぶ部分）
この2つがそろって初めて、「ちゃんと終わる再帰」になる。
どちらかが欠けると、ほぼ確実にバグかエラーか、最悪だと脆弱性になる。
いちばんやさしい再帰：カウントダウンをPythonで書く
カウントダウンの再帰関数
まずは「n から 1 までカウントダウンして表示する」関数を、再帰で書いてみよう。
def countdown(n):
if n <= 0: # ① ベースケース（終わりの条件）
print("終了")
return
print(n) # ② 今の仕事
countdown(n - 1) # ③ 再帰ステップ（問題を小さくして自分を呼ぶ）
countdown(3)
実行すると、こう表示される。
3
2
1
終了
ここから、重要な部分を一つずつ深掘りしていく。
ベースケースを深掘りする
if n <= 0: の部分がベースケースだ。
意味としては、「n が 0 以下になったら、もうこれ以上自分を呼ばずに終わる」という宣言になっている。
もしこの条件がなかったら、countdown(n - 1) は永遠に呼ばれ続ける。
n は 3 → 2 → 1 → 0 → -1 → -2 → … と減り続け、Python は最終的に
RecursionError: maximum recursion depth exceeded
というエラーを出す。
これは「再帰の深さが限界を超えた」という意味で、スタックオーバーフローに近い状態だ。
セキュリティ・安全性の観点から言うと、「必ず終わる条件を入れる」は再帰の絶対ルールだ。
ここを雑にすると、「特定の入力を与えるとプロセスが落ちる」みたいな危険なコードが生まれる。
再帰ステップを深掘りする
countdown(n - 1) の部分が再帰ステップだ。
ここでやっていることは、「今の n を1つ減らして、残りの仕事を未来の自分に任せる」という動きだ。
countdown(3) は「3を表示して、あとは countdown(2) に任せる」countdown(2) は「2を表示して、あとは countdown(1) に任せる」countdown(1) は「1を表示して、あとは countdown(0) に任せる」
そして countdown(0) でベースケースに到達し、「終了」と表示して終わる。
この「自分は一歩だけ進めて、残りは再帰呼び出しに任せる」という感覚が、再帰のコアにある。
裏側で何が起きているか：コールスタックとPython
コールスタックという舞台裏
Pythonは関数を呼び出すたびに、「どこから呼ばれたか」「そのときの変数の値は何か」といった情報をスタックに積み上げていく。
これを「コールスタック」と呼ぶ。
countdown(3) の流れを、コールスタックのイメージで追ってみよう。
最初に countdown(3) が呼ばれる
その中で countdown(2) が呼ばれる
その中で countdown(1) が呼ばれる
その中で countdown(0) が呼ばれる
このとき、スタックには
countdown(3)countdown(2)countdown(1)countdown(0)
という感じで「呼び出しの履歴」が積み上がっている。
countdown(0) がベースケースで return すると、一番上の countdown(0) がスタックから消える。
次に countdown(1) に戻り、そこも処理が終わるとスタックから消え…というふうに、一段ずつ戻っていく。
これが「呼び出し元に戻る」という動きの正体だ。
再帰の深さと安全性
Pythonには「最大再帰深度」が決まっていて、デフォルトではそんなに深くない。
あまりに深い再帰をすると、さっきの RecursionError が出る。
これは単なるエラーではなく、「入力次第で簡単に落ちるコード」という意味でもある。
特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、セキュリティ的にも慎重に扱うべきだ。
アルゴリズムと再帰の関係
再帰は「アルゴリズムの表現方法」のひとつ
アルゴリズムは「問題を解く手順」だった。
その手順をコードにする方法として、大きく分けて二つある。
ループ（for, while）で書く
再帰で書く
たとえば「1 から n までの合計を求める」というアルゴリズムを考えてみよう。
ループで書く場合
def sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
再帰で書く場合
def sum_recursive(n):
if n == 0: # ベースケース
return 0
return n + sum_recursive(n - 1) # 再帰ステップ
どちらも「1 から n までの合計を求める」という同じアルゴリズムを実現している。
ただ、表現の仕方が違うだけだ。
再帰が特に強い場面の予告
再帰が本領を発揮するのは、「入れ子構造」や「木構造」を扱うときだ。
Pythonだと、ネストしたリストや辞書、ディレクトリ構造、ツリー状のデータなどが典型的な例になる。
ある要素の中に、また同じような構造が入っている
その中に、さらに同じような構造が入っている
こういう「自分と同じ形が中に入っている」構造は、再帰と相性が抜群だ。
このあたりは後半でしっかり攻める。
Pythonらしい再帰の入り口：リストをなめる
リストの合計を再帰で書く
Pythonではリストを扱うことが多いので、リストを題材にした再帰を一つだけ前半に置いておく。
def sum_list(nums, i=0):
if i == len(nums): # ベースケース：末尾まで来たら 0
return 0
return nums[i] + sum_list(nums, i + 1)
print(sum_list([1, 2, 3, 4])) # 10
ここでやっていることはシンプルだ。
「リストの末尾まで来たら合計は 0」と決める。
そうでなければ、「今の要素」＋「残りの要素の合計」として、問題を一歩だけ小さくしている。
この「今の1つ＋残りを再帰に任せる」というパターンは、Pythonで再帰を書くときの基本形になる。
後半では、これを文字列やネスト構造にも広げていく。
前半のまとめと後半へのつなぎ
ここまでの前半で、次の土台をつくった。
アルゴリズムは「問題を解くための手順書」であり、文法とは別に鍛えるべき「考え方」であること。
再帰関数は「自分自身を呼び出す関数」だが、本質は「大きな問題を同じ形の小さな問題に分解する」ことにあること。
再帰には「ベースケース」と「再帰ステップ」という2本柱が必須で、これを間違えると RecursionError や危険なコードになること。
Pythonではコールスタックの上で再帰が動いており、深くなりすぎると最大再帰深度に引っかかること。
カウントダウンやリストの合計など、シンプルな例で「自分は一歩だけ進めて、残りは再帰に任せる」という感覚をつかんだこと。
後半では、ここから一歩進んで、
階乗・フィボナッチ数列などの典型的な再帰アルゴリズム
文字列やネストしたリスト・辞書を再帰で処理する方法
再帰とループのどちらを選ぶべきかという判断軸
再帰を書くときの「思考の型」と、よくある落とし穴
このあたりを、Pythonコードをガンガン書きながら深掘りしていく。
