単一後継関数を持つ再帰プログラムからの再帰除去

概要

論文の詳細を見る
再帰プログラムは反復プログラムに比べて書きやすく読みやすい場合が多いが,計算機で実行する際には手続呼び出しとスタック操作が必要である.そのため,インライン展開ができない,局所参照性が悪いなどのプログラム最適化上の問題を引き起す.したがって,再帰プログラムを,計算量を増加させずにスタックを使用しない反復プログラムに変換する再帰除去法が1970年代より研究されてきた.我々は1998年に,線形再帰プログラム(再帰呼び出しを実質的に1つしか含まない再帰プログラム)に対して,累積関数を用いた再帰除去法を提案した.本発表は,その再帰除去法を単一後継関数を持つ非線形再帰プログラムにも適用できるように拡張するものである.ただし,単一後継関数を持つ再帰プログラムとは,f(x):if p(x)then b(x)else a(c(x),f(d(x)),f(d^2(x)),...,f(d^n(x)))の形式のプログラムである.まず単一後継関数を持つ再帰プログラムのための累積関数を定義し,その例を示す.次に累積関数を用いた再帰除去法を提案する.また,累積関数を利用した再帰プログラムの閉式化法も提案する.
一般社団法人情報処理学会の論文
2002-09-15