Swiftでの再帰処理

Swiftでは関数型でほとんど行けるようなので，ループ構文を無視してなんでも再帰で書きたくなる衝動にかられたりします．そこで，どの程度再帰が使いやすいか調べてみました．

普通の再帰関数

func fibonacci(n: Int) -> Int {
 return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1)
}

普通に動きます．まあ，今時当たり前ですね．

末尾再帰

func fib_iter(n: Int, p: Int, pp: Int) -> Int {
	if n == 0 { return 0 }
    return (n == 1) ? p : fib_iter(n - 1, p + pp, p)
}

これも普通に動きます．コンパイラの最適化でループに変換されていました．よしよし．

内部関数で再帰

上の末尾再帰は内側に隠したくなりますよね．

func fibonacci(n: Int) -> Int {
    func fib_iter(n: Int, p: Int, pp: Int) -> Int {
        return (n == 1) ? p : fib_iter(n - 1, p + pp, p)
    }
    return n < 2 ? n : fib_iter(n, 1, 0)
}

error: cannot reference a local function from another local function
        return (n == 1) ? p : fib_iter(n - 1, p + pp, p)
                              ^

これはダメでした．むむむ．ありがちなパターンだと思うのですが．

クロージャで再帰

<追記> コメントで情報をもらってクロージャの再帰の記述方法がわかりました． 別ポストにてメモしました → Swiftのクロージャで再帰

let fib = {(n: Int) -> Int in
    return n < 2 ? n : fib(n - 1) + fib(n - 2)
}

error: variable used within its own initial value

これもダメでした．こういうのはletrecがないと無理ですね．

サブスクリプトで再帰！？

試しにやってみたところ，

struct Fib {
    subscript(n: Int) -> Int {
        return n < 2 ? n : self[n - 1] + self[n - 2]
    }
}

なんと大丈夫でした．面白いですね．こういう風にかけると構造体Fibがあたかもレイジーな配列のように見えてきます．
じゃあ，末尾再帰サブスクリプトとの組み合わせは，

struct Fib {
    subscript(n: Int) -> Int {
        return n < 2 ? n : self[n, 1, 0]
    }
    subscript(n: Int, p:Int, pp: Int) ->Int {
        return (n == 1) ? p : self[n - 1, p + pp, p]
    }
}

ばっちりいけます．サブスクリプトでは内部では本当にただの関数なんですね．

サブスクリプトでメモ化はできるか？

悪乗りついでに，

struct FibMemo {
    var memo = [Int]()
    subscript(n: Int) -> Int {  // 0,1は省略
            if n < memo.count {
                return memo[n]
            } else {
                let m = self[n - 1] + self[n - 2]
                memo.append(m)
                return m
            }
        }
    }
}

error: immutable value of type '[(Int)]' only has mutating members named 'append'

これはappendで怒られました．サブスクリプト（コンピューテッドプロパティ）のgetはリードオンリーなのでvarな変数も変更不能な定数扱いなんですね．メモ化ができれば面白かったんですが．

まとめ

• 普通の再帰関数は書けますが，内部関数やクロージャでは再帰はダメなのであまり使い勝手はよくないですね．素直にループ構文を使いましょう．
• サブスクリプトでも再帰できるのは意外でした．面白いですが，使い道がピンときません．

以上です．