タビュレーション再帰法と項書換え系の等価変換への応用

スポンサーリンク

概要

論文の詳細を見る
関数型プログラミングにおいては、プログラムが原始再帰法や経過値再帰法の形で書かれることが少なくない。しかし、このような形で書かれたプログラムでは実行時に冗長な計算が行なわれることが多く、効率的には必ずしも最良のものではない。本稿では、より効率の良いプログラムを与えるタビュレーション再帰法を定式化する。例えば、原始再帰法の形のリストリバースのプログラムや経過値再帰法の形のフィボナッチ数列のプログラムに対して、それぞれ、より効率の良いプログラムが知られているが、それらはタビュレーション再帰法の形になっている。さらに本稿では、原始再帰法や経過値再帰法によるプログラムをタビュレーション再帰法によるものへと変換する問題についていくつかの結果を報告する。
一般社団法人情報処理学会の論文
1991-02-25

著者

関連論文

もっと見る

スポンサーリンク