再帰処理

再帰処理とは

再帰関数、再帰呼び出しとも言われます。

再帰処理とは関数の処理の中で、自分自身をさらに呼び出す処理のことを言います。
以下のような状態です。

func recursiveFunction(number: Int) -> Int {
    ...
    return recursiveFunction(number: number - 1)
}

recursiveFunctionの中でさらにrecursiveFunctionが呼び出されています。
この結果がどうなるかというと、呼び出されたrecursiveFunctionがまたさらにrecursiveFunction呼び出し、さらに....

というように無限に自分自身を呼び出すような構造になっています。

これでは処理がここで止まってしまい、プログラムが先に進まないので終了条件を与えます。

以下の例題で解説します。

例題

再帰処理を使って階乗の計算結果を返す関数を作成してください。
※負の数が指定された場合は0を返すようにしてください。

func factorial(number: Int) -> Int {
    ...
}
let result = factorial(number: 5)
print(resut)

120

回答例

func factorial(number: Int) -> Int {
    if number < 0 {
        return 0
    }

    if number == 0 {
        return 1
    }

    return number * factorial(number: number - 1)
}

解説

if number < 0は負の数の場合の処理で、どちらかというとエラー処理なので再帰とはあまり関係ありません。

if number == 0 {
    return 1
}

こちらが終了条件になります。

return number * factorial(number: number - 1)

ここで自分自身を再度呼び出していますが、引数にはnumber - 1と1引いた値を与えています。

最初にfactorial(number: 5)という呼び出しをしたとします。
するとこの部分は

return 5 * factorial(number: 4)

となります。
factorial(number: 4)の部分は

return 4 * factorial(number: 3)

となります。
つまりfactorial(number: 5)は

return 5 * 4 * factorial(number: 3)

という結果を返すことになります。
factorial(number: 3)も同様なので、どんどん引数が減算されていき0となります。

引数が0となったタイミングで以下の処理に入り1がreturnされループが止まります。

if number == 0 {
    return 1
}

結果、factorial(number: 5)の呼び出しはreturn 5 * 4 * 3 * 2 * 1 * 1となり階乗計算した結果が返るというわけです。

再帰処理はループ処理の１つだと思ってもらえればいいです。
ちなみに再帰で書けるものはwhileでも書けるので最終的には読みやすい方を採用してください。

練習問題

練習問題１

漸化式：a[n+1] = a[n] + 5
初項：a[0] = 0

上記の等差数列の第N項を求める関数を再帰処理で実装してください。
※N < 0の場合はnilを返してください。

回答例はこちら

練習問題２

累乗計算を行う関数を再帰処理で実装してください。

回答例はこちら

練習問題３

フィボナッチ数列の第N項の値を求める関数を再帰処理で実装してください。

回答例はこちら

最後に

別の問題は以下に掲載しています。
また本記事とは別でプログラミング未経験からiOSアプリ開発が行えるようになることを目的とした記事を連載しています。
連載も以下にまとめていますのでそちらも是非もご覧ください。
http://naoyalog.com/