再帰関数の理解にチャレンジする
プログラミングの壁って、いろいろあると思うのですが、中でも私にとって再帰関数は手ごわい。
プログラミングを勉強しだして、最初に当った壁が配列でした。単に、高校数学の行列と同じ概念なのですけど。
その次の大きな壁として立ちはだかるのが、オブジェクト指向や再帰関数、ポインタ、ソートアルゴリズムとか。
今日は、再帰関数の理解にチャレンジしてみたので、その記録。
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}")
■この記事のトラックバックURL:
http://www.mapee.jp/mpe334/mt-tb.cgi/464
以下のHTMLタグをトラックバック送信元ページ内に挿入して下さい。
※この記事へのリンクがない、また関連のないページからのトラックバックは反映されませんので、ご了承下さい。
