はじめに
私は現在エンジニアの仕事をしつつ、業務外でコンピュータサイエンスの基礎を学習しています。
エンジニア歴は2年未満で、主に触っている言語は TypeScript / Python / Google Apps Script です。
今回はCSの基礎概念のひとつである 「再帰（recursion）」 を学習したので、アウトプットとしてまとめます 
再帰を一言で説明すると
「関数が、自分自身を呼び出すことで問題を小さく分解して解く方法」 です。
もう少し丁寧に言うと、
ある関数がその内部処理において、自身を関数として呼び出すことを「再帰」と呼びます。
具体例で理解する：掛け算を足し算に分解する
たとえば、7 × 5 を「掛け算を使わずに」求めるとします。
ポイントはこれです。
- 7 × 5 は、7 × 4 に 7 を足したもの
- 7 × 4 は、7 × 3 に 7 を足したもの
- …と、どんどん「1つ小さい問題」に分解できる
つまりこう書けます。
7 * 5
= (7 * 4) + 7
= {(7 * 3) + 7} + 7
ここで、自然数 n に対して 7 * n を返す関数を multiplyBy7(n) とすると、
multiplyBy7(n) = multiplyBy7(n - 1) + 7
となります。
この 「自分自身を呼び出して1つ小さい問題を解く」 が再帰の基本形です 
再帰で絶対に外せないのが「ベースケース」
再帰を扱うときに、最も重要なのが ベースケース（base case） です。
なぜ必要？
コンピュータは無限に計算できません。
- メモリには物理的な上限がある
- いつまでも関数呼び出しが続くと、いずれ スタックオーバーフロー などで落ちる
- 例：割り切れない数（πなど）を無限の精度で扱うことは不可能
なので、再帰では必ずこう考えます。
「この処理は、どこで必ず終わる？」
この 「ここまで来たら必ず値を返して終了する条件」 がベースケースです。
ベースケースがないと何が起きる？
- 関数が自分を呼び続ける
- 終了条件がないので止まらない
- プログラム内部では止められず、外部から停止（強制終了など）が必要になることもある
実例：文字列の length を再帰で再現してみる（TypeScript）
再帰が理解できると、たとえば「文字列の長さ」を数える処理も自力で書けます。
以下は length を再帰で再現した例です。
function lengthOfString(str: string): number {
if (str === "") return 0; // ベースケース
return lengthOfString(str.slice(0, -1)) + 1;
}
まとめ：再帰を理解するコツ
再帰が苦手なときは、次の2点だけに集中すると理解が進みます。
- ベースケースは何か？（どこで終わる？）
- 再帰ステップで、問題が確実に小さくなっているか？
この2つが揃えば、再帰は「怖いもの」ではなく「分解の道具」になります 
おわりに
この記事が少しでも参考になったら、LGTM（いいね） や コメント をもらえると励みになります！
「ここが分かりづらかった」「この例も知りたい」などのフィードバックも大歓迎です