返回到Lisp中的递归函数的顶级调用

Question

我有一个递归函数,需要递归,直到找到一定的结果.然而,在我的第一次递归调用后,我的函数体中可能会做一些其他的计算或者可能再次递归.但是,如果我递归并找到我正在寻找的结果,那么我想停止我正在做的任何递归并返回该结果以避免进行不必要的计算.

在正常的递归调用中,一旦你到达被调用的函数返回的"基本情况",那么它将返回到调用它的那个,依此类推.我想知道如何在第一次调用函数时返回,而不必为所有这些中间步骤返回一些东西.

对于我的基本递归,我可以写一个这样的函数:

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

编写它是为了说明我在递归调用后运行更多计算的函数的含义.并且,正如所写,这甚至没有返回我感兴趣的值,因为我在返回我关心的值之后进行了一些打印.(注意:return-from命令在这里是无关紧要的,因为我可以在它的位置写"x".当我尝试在下面的第二个例子中返回顶级递归时,它就是在那里画出相似之处.)

现在,如果我想抛弃所有额外的"递归!" 打印我可以将所有内容包含在一个块中,然后返回到该块:

编辑:这是我原始示例的函数包装器.这个例子现在应该更清楚了.

(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",然后从顶层块返回,没有任何无关的打印,就像我想要的那样.但是,这似乎是获得此功能的一种非常笨重的方式.我想知道是否有一种标准或"最佳"的方式来获得这种行为.

Answer 1

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)))

较旧的是使用CATCH和THROW,它是一个更动态的构造,因此允许跨函数退出:

(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所提到的,还有更多的方法可以像这样编程控制流程.