Swiftで再帰関数を書く

Ryoichi Izumita
Sep 7, 2018 · 6 min read

再帰関数、書いたことがありますか?

私は一応あります。一応です。

この記事ではその再帰関数をSwiftでどのように書くかを説明してみようと思います。

というのも私自身が難しいと感じており、説明することで理解を深めようというのが第一の目的です。間違ってるところがあったらご指摘ください…

再帰関数とは

関数が自分自身を呼びだすことを再帰呼び出しといいます。再帰呼び出しを行う関数を再帰関数といいます。

図にすると以下のようになります。

複雑な実装では戻ったあとにまた再帰呼び出しを行うこともありますが、単純な再帰関数は図のように再帰呼び出しを1回以上繰り返した後呼び出し元に戻ってきます。

再帰関数を利用すると複雑な処理を簡単に記述できることがあります。しかし再帰呼び出しが続きすぎたり終了しない実装になっていたりするとスタックオーバーフローが発生してしまいます。

再帰が続きすぎてもSwiftでは末尾再帰最適化(ググってみてください)が行われるらしいので最適化がされるコードを書けば対応は可能です。しかし実装を間違って再帰が終了しないと、処理が終わらなくなりスタックオーバーフロー(ググって…)が発生します。

ですので再帰関数はかならず終了するように気をつけて実装する必要があります。

enumで再帰関数

enumを使った再帰関数を考えてみます。

indirect enum List<T> {
case end
case node(T, List<T>)
}

単方向リストです。

こんなイメージです。ノードは自身の値と、次のノードもしくは終端であるendへの参照を持ちます。

IntのListを作り、その合計をもとめてみます。

まず関数のひな形を作ります。

func sum(_ list: List<Int>) -> Int {
return 0
}

以下のテストが全てtrueになれば成功とします。

print(sum(.end) == 0)
print(sum(.node(3, .node(0, .end))) == 3)
print(sum(.node(1, .node(2, .node(3, .node(4, .end))))) == 10)

ではsum関数の実装を行っていきます。

まず終了条件ですが渡されたListがendであるということです。Listを引数に取る関数では無限Listを作って渡すことはできないので、必ず最後はendになります。ですのでendであれば再帰終了とすることができます。

nodeであればそのノードの値と次のList(nodeもしくはend)が利用できます。まずは自身の値を返してみます。

func sum(_ list: List<Int>) -> Int {
switch list {
case .end:
return 0
case .node(let num, let next):
return num
}
}

このようになりました。endであれば0、nodeであれば自身の値であるnumを返します。

しかしこれでは再帰呼び出しを行っていないので、はじめの値しか返していません。

再帰呼び出しをしてリストの残りも足していきましょう。

func sum(_ list: List<Int>) -> Int {
switch list {
case .end:
return 0
case .node(let num, let next):
return num + sum(next)
}
}

nextは現在のノードを含まないList<Int>ですのでこれをsum関数に渡すと残りのノードの合計が計算されます。num + sum(next)が行われていき、nextがendになるとcase .endに至り0が返されます。

List(1, 2, 3, 4, end)とすると

1+List(2, 3, 4, end)

1+2+List(3, 4, end)

1+2+3+List(4, end)

1+2+3+4+end

1+2+3+4+0

と再帰呼び出しが行われていくことになります。

この実装で全てのテストがtrueになりました。

単方向リストはノードに自分自身への参照(この場合は次のノード)を含むので再帰的データ構造になっています。再帰的データ構造の処理では再帰を利用することが多くあります。

Arrayで再帰関数

では次にArrayでの再帰を考えてみます。

Arrayでもsum関数を作ります。

func sum(_ array: [Int]) -> Int {
return 0
}

以下のテストが全てtrueになれば合格にします。

print(sum([]) == 0)
print(sum([3, 0]) == 3)
print(sum([1, 2, 3, 4]) == 10)

enumのListはendとnodeの2つに場合分けされ、endが終了の条件になりました。Arrayではどのように場合分けすればいいのでしょうか。

このような場合分けはどうでしょう。

  1. [] (空)
  2. first & rest (最初の値 & 残りの値の配列)

1は空の配列です。

2は配列に値が入っています。最初の値と残りの値の配列です。残りの値の配列は空の場合もあれば、1つ以上の値が入っていることもあります。

[]の場合→[]

[3]の場合→3 & []

[3, 8]の場合→3 & [8]→3 & 8 & []

この2つの場合分けで配列を理解することができそうです。

func sum(_ array: [Int]) -> Int {
if array.isEmpty { return 0 }
var _array = array
let first = _array.removeFirst()
return first + sum(_array)
}

単純に実装するとこのようになります。Arrayが空の場合は0を返す。値が入っている場合は最初の値を取り出して、それとsumで残りの配列の合計を計算した値を足しています。

Arrayは単方向リストより再帰の書き方が分かりにくいですが、終了の場合と再帰呼び出しを行う場合をうまく場合分けすれば再帰関数が書けることが分かりました。


以上のようにenumで作った単方向リストと配列を扱う再帰関数を実装してみました。これらは簡単な実装でしたが、たとえば2つの配列を扱う再帰関数を考えると場合分けが複雑になってきます。うまく場合分けを行うことが再帰関数を実装する上で重要なようです。

Ryoichi Izumita

Written by

iOS app programmer / Objective-C / Swift

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade