在计划中突破递归的标准方法

Question

我正在编写我的第一个计划程序.我对递归非常深入,因为我基本上解释了一个程序,它可以用于一个可以嵌套过程调用的简单机器人.

如果我发现违规,我需要停止解释程序并返回上一个有效状态.

我通过声明一个全局变量(define illegalMoveFlag 0)然后设置它来解决它set!.

它工作正常,但我想我的导师不喜欢它(因为它不是我想的功能方法)

我想到的其他方法是为我在程序中递归调用的每个函数添加一个错误参数.我不太喜欢它,因为它会使我的代码更不易读,但我想它更具"功能性".

可能还有第三种方式我没有想到吗？我的方法可以在这个范例中证明是合理的,还是基本上是代码味道？

Answer 1

停止递归的常用方法是停止递归.即,不要再调用递归函数.:-)

如果这样做太难了,另一种突破某种方法的方法是捕获顶层的延续(在开始递归之前),然后在需要"转义"时调用延续.但是,您的教练可能不喜欢这种方法.;-)

Answer 2

由于这是你的第一个Scheme程序,你可能只需要引入一个条件表达式,cond以避免在到达结尾时进一步递归.例如:

; sum : natural -> natural
;  compute the sum 0+1+...+max
(define (sum max)
  (define (sum-helper i sum-so-far)
    (if (> i max)
        sum-so-far
        (sum-helper (+ i 1) (+ sum-so-far i))))
  (sum-helper 0 0))

(display (sum 10))
(newline)

但是,如果您需要return像longjmpC中那样返回传统,则需要存储并使用转义延续.这可以这样做:

(define (example)
  (let/ec return
    (define (loop n)
      (if (= n 100000)
          (return (list "final count: " n))
          (loop (+ n 1))))
    (loop 0)))

(display (example))

如果let/ec未在您的Scheme实现中定义,则在程序前面加上:

(define-syntax let/ec 
  (syntax-rules ()
    [(_ return body ...)
     (call-with-current-continuation
      (lambda (return)
        body ...))]))

更新:

请注意,cond有一个=>变体:

(cond
  [(call-that-can-fail)
    => (lambda (a) <use-a-here>))]
  [else <do-something-else>])

如果调用成功,则执行第一个子句,并将结果绑定到a.如果调用失败,则使用else子句.