# プログラミング全般＞フリートーク

再帰関数の理解にチャレンジする

プログラミングの壁って、いろいろあると思うのですが、中でも私にとって再帰関数は手ごわい。
プログラミングを勉強しだして、最初に当った壁が配列でした。単に、高校数学の行列と同じ概念なのですけど。
その次の大きな壁として立ちはだかるのが、オブジェクト指向や再帰関数、ポインタ、ソートアルゴリズムとか。
今日は、再帰関数の理解にチャレンジしてみたので、その記録。
C言語の本を読んでて出てきた再帰関数なのですけど、Rubyで書きなおしてみる。
正の整数を引数として受け取り、上位一桁ずつ（1文字ずつ）出力するという単純な（でも、私にとっては難しい）再帰関数の例です。

# nは正の整数
def printd(n)
    if ((n / 10) != 0)
        printd(n / 10)
    end
    putc("#{n % 10}")
end
 
printd(123)

再帰関数をぱっと見て理解できる人は、ほんと尊敬。
こんな単純な再帰でも、私にとってはけっこう理解が大変です。
以下、いつも再帰関数を理解する時に私が使う方法で、再帰呼び出しの部分を、定義された関数に実引数を渡して置き換え、実際の処理の流れを追う原始的な解析方法です。
まず最初、printd(123)　が呼ばれたとき、どんな処理が起こるか。

# printd(123) が呼び出された時、n には123が入る。
if ((123 / 10) != 0)    # true
    printd(123 / 10)    # 再帰突入1回目。printd(12) 
end
putc("#{123 % 10}")

if ((123 / 10) != 0) の判定処理はtrueなので、再帰呼び出しが行われ、printd(12) が実行される。
ここも、実引数12を渡して、実際に定義された関数に置き換える。

# printd(123) が呼び出された時、n には123が入る。
if ((123 / 10) != 0)    # true
    # printd(123 / 10)    再帰突入1回目。printd(12)
    if ((12 / 10) != 0)        # true
        printd(12 / 10)        # 再帰突入2回目。printd(1) 
    end
    putc("#{12 % 10}")
end
putc("#{123 % 10}")

if ((12 / 10) != 0) の判定処理はtrueなので、再び再帰的にprintdが呼び出されて、printd(1) が実行される。今度は、実引数1を渡して、置き換える。

# printd(123) が呼び出された時、n には123が入る。
if ((123 / 10) != 0)    # true
    # printd(123 / 10)    再帰突入1回目。printd(12) 
    if ((12 / 10) != 0)        # true
        # printd(12 / 10)    再帰突入2回目。printd(1) 
        if ((1 / 10) != 0)    # false。
            printd(1 / 10)    # 実行されない。再帰終了。
        end
        putc("#{1 % 10}")
    end
    putc("#{12 % 10}")
end
putc("#{123 % 10}")

printd(1) が実行された場合、if ((1 / 10) != 0) は、falseとなり、ここで再帰呼び出しが完了することになります。
したがって、上記のコードが最終的に呼び出される実際の処理の流れとなり、これならif文と算術演算、出力だけのコードなので理解しやすい。
実際に、引数として渡された正の整数が、上位一桁から1文字ずつ出力される流れも分かります。

以下の、再帰呼び出し、および実際の処理の流れ、双方のコードは「123」と同じ出力になります。
コピペして、codepadで、Rubyを選択して実行すれば、確認できます。

再帰呼び出し

def printd(n)
    if ((n / 10) != 0)
        printd(n / 10)
    end
    putc("#{n % 10}")
end
 
printd(123)

実際の処理の流れ

# printd(123) が呼び出された時、n には123が入る。
if ((123 / 10) != 0)    # true
    # printd(123 / 10)    再帰突入1回目る。printd(12) 実行
    if ((12 / 10) != 0)        # true
        # printd(12 / 10)    再帰突入2回。printd(1) 実行
        if ((1 / 10) != 0)    # false。
            printd(1 / 10)    # 実行されない。再帰終了。
        end
        putc("#{1 % 10}")
    end
    putc("#{12 % 10}")
end
putc("#{123 % 10}")

>> 次の記事 : デトロイトメタルシティにはまる