再帰 ― 自分自身を呼ぶ関数

導入

関数は、自分自身を呼び出すこともできます。これを再帰といいます。階乗やフィボナッチなど、同じ形の小さな問題に分けられる計算に向いています。

説明

再帰には必ず「これ以上分けない終わりの条件（ベースケース）」が必要です。それが無いと無限に呼び出して止まりません。階乗（n! = n × (n-1) × ... × 1）を例にします。

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;          // ベースケース（終わり）
    return n * factorial(n - 1);   // 自分自身を呼ぶ
}

int main() {
    cout << factorial(5) << endl;   // 120
    return 0;
}

factorial(5) は 5 * factorial(4)、それが 5 * 4 * factorial(3)……と展開され、最後に 1（ベースケース）へ到達して、こんどは結果を掛けながら戻っていきます。行きは分解、帰りは掛け算です。

flowchart TB
  f5["factorial(5)"] -->|"5 ×"| f4["factorial(4)"]
  f4 -->|"4 ×"| f3["factorial(3)"]
  f3 -->|"3 ×"| f2["factorial(2)"]
  f2 -->|"2 ×"| f1["factorial(1) = 1<br/>（ここで止まる）"]
  f1 -.->|"1"| f2
  f2 -.->|"2"| f3
  f3 -.->|"6"| f4
  f4 -.->|"24"| f5
  f5 -.->|"120"| ans["答え 120"]

やってみよう

factorial に渡す数を変えて結果を確かめましょう。大きすぎる数は値があふれる（オーバーフロー）ので、小さめの数で試してください。

演習

1 から n までの合計を再帰で求める関数 sumTo を定義し、sumTo(10) を表示してください（結果は 55）。