【プログラミング初心者】Swift練習問題~再帰処理~回答例

練習問題

練習問題1

回答例

func getArithmeticSequence(index: Int) -> Int? {
    // エラー
    guard index >= 0 else {
        return nil
    }

    if index == 0 {
        return 0
    }

    // アンラップ
    guard let preValue = getArithmeticSequence(index: index - 1) else {
        return nil
    }

    return preValue + 5
}

解説

guard index >= 0 else {
    return nil
}

エラー処理です。
a[-1]という値は存在しないのでnilを返します。

if index == 0 {
    return 0
}

ここが終了条件になります。
初項であるa[0]: 0を値として返します。

guard let preValue = getArithmeticSequence(index: index - 1) else {
    return nil
}

ここで再帰呼び出しをします。
戻り値がオプショナル型であるためアンラップしています。
値がnilだった場合return nilとなりますが、indexが負の数以外nilとはならないので呼び出されません。

return preValue + 5

a[n] = a[n-1]+5を求めます。
preValueは第N-1項の値であるので第N項の値はpreValue + 5で求まります。

練習問題2

回答例

func power(base: Double, exponential: Int) -> Double {
    if exponential == 0 {
        return 1.0
    }

    if exponential > 0 {
        return base * power(base: base, exponential: exponential - 1)
    } else {
        return power(base: base, exponential: exponential + 1) / base
    }
}

解説

累乗は指数が正の場合掛け算、負の場合割り算、0の場合は1となります。
これを漸化式で表すと以下になります。累乗の漸化式

a[n] = r × a[n-1] (n > 0)
a[n] = 1/r × a[n+1] (n < 0)
a[0] = 1

まず終了条件となるn = 0の場合の処理を書きます。

if exponential == 0 {
    return 1.0
}

指数の値の正負で計算方法が変わるため場合分けし、漸化式の通りに処理します。正の場合

return base * power(base: base, exponential: exponential - 1)

負の場合

return power(base: base, exponential: exponential + 1) / base

最終的にどちらも指数が0となり終了条件を満たし処理が完了します。

練習問題3

回答例

func getRecursiveFibonacci(index: Int) -> Int? {
    guard index >= 0 else {
        return nil
    }

    if index == 0 {
        return 0
    } else if index == 1 {
        return 1
    } else {
        guard
            let pre1Value = getRecursiveFibonacci(index: index - 1),
            let pre2Value = getRecursiveFibonacci(index: index - 2) else {
                return nil
        }
        return pre1Value + pre2Value
    }
}

解説

実装の仕方はこれまでと同じです。フィボナッチ数列の漸化式

a[n] = a[n-1] + a[n-2]
a[0] = 0
a[1] = 1

負の数はフィボナッチ数列にはないのでnilを返します。

guard index >= 0 else {
    return nil
}

フィボナッチ数列の場合初期値が第1項と第0項で必要になるため終了条件がそれぞれ必要となります。

if index == 0 {
    return 0
} else if index == 1 {
    return 1
}

これはa[2]を求めるときを考えればわかります。
a[2] = a[1] + a[0]です。
もしa[1]が定義されていなければ、ここも再帰で求めようとしてa[1] = a[0] + a[-1]を計算しようとします。
ですがa[-1]は定義できないため計算することができません。
これを防ぐために終了条件として第1項と第0項を定義しています。

あとは漸化式に当てはめて計算します。

guard
    let pre1Value = getRecursiveFibonacci(index: index - 1),
    let pre2Value = getRecursiveFibonacci(index: index - 2) else {
        return nil
    }
return pre1Value + pre2Value

最後に

再帰のコツは終了条件と1つ前の処理との関係を明確にすることです。
今回はわかりやすいため漸化式として前後関係が明確な数列を扱いましたが、再帰は数列だけではありません。
別途数列以外の問題も投稿していきます。
以上。

コメント

タイトルとURLをコピーしました