Lispの再帰関数のトップレベルの呼び出しに戻る

2014年10月10日に質問されました。  ·  閲覧回数 1k回  ·  ソース

Nyles picture
2014年10月10日

特定の結果が見つかるまで再帰する必要がある再帰関数があります。 ただし、最初の再帰呼び出しの後の関数の本体で、他の計算を実行するか、場合によっては再度再帰する可能性があります。 しかし、再帰して探している結果が見つかった場合は、これまで行ってきた再帰をやめて、不要な計算を行わないようにその結果を返したいと思います。

通常の再帰呼び出しでは、呼び出した関数に返される「基本ケース」に到達すると、それを呼び出した関数に返されます。 関数が最初に呼び出されたときに戻る方法を知りたいのですが、これらすべての中間ステップで何かを返す必要はありません。

私の基本的な再帰では、次のような関数を書くことができます。

(defun recurse (x)
   (if (= x 10)
       (return-from recurse x)
       (progn (recurse (+ x 1)) (print "Recursed!")))))
(recurse 1)

これは、再帰呼び出しの後にさらに多くの計算を実行する関数について私が何を意味するかを説明するために書かれています。 そして、書かれているように、私が気になる値を返した後にいくつかの印刷を行うので、これは私が興味を持っている値を返すことさえしません。 (注:return-fromコマンドは、その場所に「x」と書くことができるため、ここでは無関係です。以下の2番目の例でトップレベルの再帰に戻ろうとするときに、類似点を描画するためだけにあります。)

さて、もし私がそれらの余分な「Recursed!」をすべて捨てたいのなら。 印刷すべてをブロックに入れて、代わりにそのブロックに戻ることができます。

編集:これが私の元の例の関数ラッパーです。 この例は、より明確になるはずです。

(defun recurse-to-top (start)
  (block top-level
    (labels ((recurse (x)
               (if (= x 10)
                   (return-from top-level x)
                   (progn (recurse (+ x 1)) (print "Recursed!")))))
      (recurse start))))

そして、このブロックの実行は、10が「見つかる」まで続き、その後、私が望んでいたように、余分な印刷を行わずにトップレベルのブロックから戻ります。 しかし、これはこの機能を取得するための本当に不格好な方法のようです。 このタイプの動作を取得するための標準的な方法または「最良の」方法があるかどうかを知りたいです。

回答

Rainer Joswig picture
2014年10月10日
6

DEFUNすでに字句ブロックを設定しています:

(defun recurse (start)
  (labels ((recurse-aux (x)
             (case x
               (10 (return-from recurse x))
               (15 x)
               (otherwise
                 (recurse-aux (+ x 1))
                 (print "Recursed!")))))
    (recurse-aux start)))

古いのはCATCHTHROW 。これはより動的な構成であるため、関数間で終了できます。

(defun recurse (start)
  (catch 'recurse-exit
    (recurse-aux start)))

(defun recurse-aux  (x)
  (case x
    (10 (throw 'recurse-exit x))
    (15 x)
    (otherwise
     (recurse-aux (+ x 1))
     (print "Recursed!")))))
      (recurse-aux start))))

Larsが述べたように、このように制御フローをプログラムする方法はさらにたくさんあります。

Lars Brinkhoff picture
2014年10月10日
3

ある種の非ローカル出口が必要です。 いくつかの選択肢があります: return-fromgothrowsignal

多分これのいくつかのバリエーション?

(defun recurse (x &optional (tag 'done))
  (catch tag
    (when (= x 10)
      (throw 'done x))
    (recurse (1+ x) nil)
    (print "Cursed!")))

不必要なキャッチがたくさん起こっているかもしれませんが、私はそれがあなたが望むことをすることを信じています。

Lispの場合と同様に、問題に最適な言語があることを想像し、その言語でプログラムを作成することができます。 例:

(defun recurse (x)
  (top-level-block recurse
    (when (= x 10)
      (return-from-top-level recurse x))
    (recurse (1+ x))
    (print "Cursed!")))

次に、新しいマクロtop-level-blockreturn-from-top-levelを実装するためのプログラミングの簡単な問題があります

不完全なサンプルコードは次のとおりです。

(defmacro top-level-block (name &body body)
  `(if (boundp ',name)
       (progn ,@body)
       (catch ',name
         (let ((,name t))
           (declare (special ,name))
           ,@body))))

(defmacro return-from-top-level (name value)
  `(throw ',name ,value))