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

#練習問題
##練習問題１
###回答例

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で求まります。

##練習問題２
###回答例

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の場合は１となります。
これを漸化式で表すと以下になります。

累乗の漸化式

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

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

##練習問題３
###回答例

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
}

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

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]は定義できないため計算することができません。
これを防ぐために終了条件として第１項と第０項を定義しています。

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

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

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