再帰関数

Question

再帰関数を使ったコードについて質問です。

def search( )
  (中略)
 ある作業をする
 search(次)    # 次を探索 
 作業をする前の状態に戻す
  (中略)
end

「作業をする前の状態に戻す」という処理を入れるような例は
よくあるのでしょうか？

例えば、こんなパターンがあります。

def search( )  # 次のステップに進むのに、２つの場合分けがある
  (中略)
 場合１の作業をする
 search(次)    # 次を探索
 作業をする前の状態に戻す
  (中略)
 場合２の作業をする
 search(次)    # 次を探索
 作業をする前の状態に戻す
  (中略)
end

Answer 1

「作業をする前の状態に戻す」 ような処理を再帰でやるかといわれると、やりません。

それ以前に、再帰自体をまず使いません。
これは、再帰は流れが追いづらく分かりにくくなりがちなのと、言語にもよりますが、メモリーの消費が多くなってしまうためです。使うのはよほどの場合で、数列や木構造のように再帰で書いた方がずっとわかりやすくなるといった時だけです。
再帰で複雑な処理をやろうとしているのであれば、おそらく、わかりにくいコードになるはずです。

原理的には再帰処理は必ずループで書くことができます。また、 Ruby では yield とブロックもあります。
具体的にどういったことがしたいのかよくわからないのですが、ブロックで書いた方が分かりやすくなるケースのような気はします。

Answer 2

再帰処理の中で起こる副作用を無しにしてしまう　という例は稀だと思います。

なぜなら、
トップレベルで呼び出した このメソッドの実行前後で何も副作用が残らない
とすると
このメソッドを呼び出す意味がないことになりますから。
(stdout やログ出力のような 「作業をする前の状態に戻す事が困難な事」の痕跡を残すことしかできないことになります。)

私が質問の意図を理解できていないのかもしれません。

Comments

[manman]

場合分けがあるcaseを質問分に追加しましたので、このようなcaseはどうでしょうか？

Answer 3

質問の意図が不明ですが、

def foo(arg)
  中略
  foo(xxx)
  中略
end

は、再帰の典型というか、再帰の定義です。

「作業をする前の状態に戻す」という処理を入れるのが再帰の典型かという意図の質問であれば、典型ではありません。

Comments

[manman]

質問の仕方がまずかったので、修正しました。

[otn]

具体的なコードでないと、抽象的すぎて、アドバイス不可能です。
書かれたレベルの抽象的な一般論で言うと、「作業をする前の状態に戻す」という処理を入れるような例は、まず無いと思います。
アドバイスが欲しければ、コードを載せて、「もっとわかりやすい書き方はないか？」という風な質問を改めてしてください。