ループを再帰関数にする考え方

ループで書かれたものを再帰で書くとたいてい読みづらくなるので、
練習問題として出された時ぐらいしか役に立たない気がするが、
ループで書かれた処理を再帰関数に置き換える際の考え方を書いてみる。

コードは模擬コードです。

真面目な考え方

もともとのアルゴリズムを漸化式のような形に考え直す。以上。
例えば階乗なら
Fact(n) = n × (n-1) × … × 1
を

Fact(n) = n × Fact(n-1) (if n > 1)
        = 1             (otherwise)

のようにする。ほら再帰だ。

以下、不真面目な方法。

ループ処理

ループを使った処理は大体こんな感じに解釈できる。

X x = x0;
while(true){
    if(isA(x))
        return A(x);
    x = Next(x);
}

要するに

/*
状態の初期化
*/
while(true){
    /*
    ループを抜ける部分
    */

    /*
    状態の再代入
    */
}

例えば、階乗は

uint Fact(uint n){
    uint result = 1;
    for(uint i = 2; i <= n; i++){
        result = result * i;
    }
    return result;
}

こうなる

uint Fact(uint n){
    uint result = 1;
    uint i = 2;
    while(true){
        if(i > n)
            return result;

        result = result * i;
        i = i + 1;
    }
    //ここにもreturnないと言語・環境によっては怒られるが
    //こまけぇこたぁいいんだよ！
}

再帰への置き換え

Y Func(P p){
    X x = Initialize(p);
    while(true){
        if(isA(x))
            return A(x);    
        x = Next(x);
    }
}

のループ部分を再帰に置き換えるとこうなる(多分)

Y Func(P p){
    X x = Initialize(p);
    return RecFunc(x);
}

Y RecFunc(X x){
    if(isA(x))
        return A(x);
    return RecFunc(Next(x));
}

どちらも
「条件を満たしていれば抜ける、さもなくば状態を更新してもう一度」
という構造になっている。

例

階乗

uint Fact(uint n){
    uint acc = 1;
    uint i = 2;
    while(true){
        if(i > n)
            return acc;

        acc = acc * i;
        i = i + 1;
    }
}

uint Fact(uint n){
    uint acc = 1;
    uint i = 2;
    return FactRec(acc, i, n);
}

uint FactRec(uint acc, uint i, uint n){
    if(i > n)
        return acc;
    // Next:
    // acc = acc * i;
    // i = i + 1;
    // n = n;
    return FactRec(acc * i, i + 1, n);
}

バイナリーサーチ

ループ版

bool BinarySearch(int[] arr,int value){
    int left = 0;
    int right = arr.Length - 1;

    while(left <= right){
        int mid = (left + right) / 2;
        if (arr[mid] == value) {
            return true;
        }
        if (arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

引数と戻り値

ループで使う値のうち、ループ外で宣言されている変数は
arr,value,left,rightで、
大本の返り値の型はboolなので、
置き換えた関数の引数と戻り値はこうなるはず。

bool BinarySearchRec(int[] arr, int value, int left, int right);

置き換え

ループを中断して値を返す状況は

while(left <= right){
    //...
}
return false;

すなわち

if(left > right)
    return false;

もうひとつ

int mid = (left + right) / 2;
if (arr[mid] == value) {
    return true;
}

まとめて、

if(left > right)
    return false;
int mid = (left + right) / 2;
if (arr[mid] == value) {
    return true;
}

また、ループを続行する状況は

if (arr[mid] < value) {
    left = mid + 1;
} else {
    right = mid - 1;
}

つまり変換するとこうなるはず。

if (arr[mid] < value) {
    return BinarySearchRec(arr, value, mid + 1, right);
} else {
    return BinarySearchRec(arr, value, left, mid - 1);
}

再帰版

まとめると

bool BinarySearch(int[] arr, int value){
    int left = 0;
    int right = arr.Length - 1;

    return BinarySearchRec(arr, value, left, right);
}

bool BinarySearchRec(int[] arr, int value, int left, int right){
    if(left > right)
        return false;
    int mid = (left + right) / 2;
    if (arr[mid] == value)
        return true;

    if (arr[mid] < value) {
        return BinarySearchRec(arr, value, mid + 1, right);
    } else {
        return BinarySearchRec(arr, value, left, mid - 1);
    }
}