再帰関数

読了目安 約3分

自分自身を呼ぶ関数。基底ケースと再帰ケース、呼び出しのトレース、スタックオーバーフロー。

関数は、自分自身を呼び出せます。 自分自身を呼ぶ関数を再帰関数と呼びます。

自分自身を呼ぶ

1 から n までの合計は、「1 から n-1 までの合計」に n を足したものです。 この言い換えを、そのまま関数にできます。

func sum(_ n: Int) -> Int {
    if n == 0 {
        return 0
    }
    return sum(n - 1) + n
}

print(sum(10))

基底ケースと再帰ケース

再帰関数は 2 つの部分でできています。

• 基底ケース: これ以上呼び出さずに答えを返す部分 (n == 0 なら 0)
• 再帰ケース: 少し小さくした自分を呼び、その結果から答えを組み立てる部分

基底ケースを忘れると呼び出しが止まらなくなり、プログラムが落ちます。

呼び出しの流れを追う

sum(3) は、呼び出しが 1 段ずつ深くなってから、答えを持って戻ってきます。

sum(3)
└─ sum(2) を呼ぶ
   └─ sum(1) を呼ぶ
      └─ sum(0) を呼ぶ → 基底ケース。0 を返す
      sum(1) = 0 + 1 → 1 を返す
   sum(2) = 1 + 2 → 3 を返す
sum(3) = 3 + 3 → 6 を返す

print を入れると、この流れを実際に観察できます。

func sum(_ n: Int) -> Int {
    print("sum(\(n)) が呼ばれました")
    if n == 0 {
        return 0
    }
    let result = sum(n - 1) + n
    print("sum(\(n)) は \(result) を返します")
    return result
}

print(sum(3))

試してみよう: sum(3) を sum(5) に変えて、呼び出しが 2 段深くなる様子を見てください。

階乗

n の階乗 (1 から n までの積) も同じ形で書けます。

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

print(factorial(5))

スタックオーバーフロー

関数を呼ぶたびに、「どこへ戻るか」の情報がスタックという領域に積まれます。 深すぎる再帰はこの領域を使い切り、実行時エラーで落ちます。

print(sum(1_000_000))   // 深すぎる再帰でクラッシュする

数十万段を超えそうな再帰は、ループで書き直すのが安全です。 同じ引数の結果を記録して使い回すメモ化という工夫は、Part 4 の動的計画法で登場します。

学びどころ

演習

会社に N 人の社員がいて、社員 1 が社長です。 社員 2 から社員 N には、それぞれ直属の上司が 1 人います (上司の番号は自分より小さい)。

部下のいない社員は、報告書を 1 枚書いて上司に提出します。 部下のいる社員は、部下たちから受け取った枚数に自分の 1 枚を加えて提出します。 各社員が提出する枚数を、社員 1 から順に 1 行ずつ出力してください (社長は会社の外へ提出すると考えます)。

1 行目に N、2 行目に社員 2 から N の上司の番号が空白区切りで入力されます。 入力例では、社員 1 の部下が 2 と 3、社員 2 の部下が 4 と 5 です。

スターターには、社員 i の部下の一覧 children[i] を作るところまで書いてあります。 「社員 i の枚数 = 1 + 部下たちの枚数の合計」が、再帰の形そのものです。

制約: 2 ≤ N ≤ 50

入力例:
5
1 1 2 2

出力例:
5
3
1
1
1

let n = Int(readLine()!)!
let p = readLine()!.split(separator: " ").map { Int($0)! }

// children[i] = 社員 i の直属の部下の一覧
var children = [[Int]](repeating: [], count: n + 1)
for i in 2...n {
    children[p[i - 2]].append(i)
}

func sheets(_ i: Int) -> Int {
    var total = 1
    for c in children[i] {
        total += sheets(c)
    }
    return total
}

for i in 1...n {
    print(sheets(i))
}