読者です 読者をやめる 読者になる 読者になる

What we talk about when we talk about Technology

技術について語ります。

一般的な再帰に対するデザインレシピ

Design Recipe

前回の再帰に対するデザインレシピはさらっとした書き方であった。
データの構造自体が再帰を含む場合(リスト等)であれば、
その書き方で十分対応できることが多いが、
一般的なデータ構造の場合はもう少し掘り下げたガイドラインがないと、
再帰を含む関数定義が困難を伴うものになる。

以下、一般的な再帰の場合考慮すべき点を述べたデザインレシピである。

テンプレート
自明に答えが出るケースとそれ以外のケースに場合分けする。

if (* 自明に答えが出るケースの条件 *)
then (* 自明に答えが出るケース *)
else (* それ以外のケース *)

本体

  • 自明に答えがでるケースの条件
  • 自明な答え
  • 部分問題の作り方
  • 部分問題から全体問題を解く方法

の4点を考慮する。
部分問題は1つとは限らない。

最後に停止性の議論をする。停止性は以下の2点を確認。
(停止性は決定不能問題なので、ガイドラインにすぎない。)

  • 部分問題がもとの問題より簡単になっていること
  • 繰り返しにより、有限回で自明なケースに帰着すること