8

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

如果我发现违规，我需要停止解释程序并返回最后一个有效状态。

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

它工作正常，但我猜我的导师不会喜欢它（因为我猜它不是功能性方法）

我考虑过的其他方法是在程序中递归调用的每个函数中添加一个错误参数。我不太喜欢它，因为它会使我的代码的可读性大大降低，但我想它更“实用”。

有没有我没有想到的第三种方式？我的方法在这种范式中是否合理，或者它基本上是一种代码味道？

4

5 回答 5

5

停止递归的常用方法是停止递归。即，不再调用递归函数。:-)

如果这太难了，另一种突破的方法是在顶层捕获一个延续（在你开始递归之前），然后在你需要“转义”时调用延续。不过，您的讲师可能不喜欢这种方法。;-)

于 2013-02-22T22:37:51.937 回答
5

由于这是您的第一个 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像在 C 中一样返回传统longjmp，则需要存储和使用转义延续。这可以这样做：

(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 子句。

于 2013-02-23T10:04:31.363 回答
2

您可能想使用内置过程error，如下所示：

(error "Illegal move") ; gives ** Error: Illegal move

这将引发异常并停止解释程序（尽管我怀疑这可能不是您想要的）。

您还可以提供其他参数，如下所示：

(error "Illegal move: " move) ; gives ** Error: Illegal move: <move>
于 2013-02-22T22:37:52.713 回答
1

您可以使用延续退出递归（或从任何其他进程）。在不了解更多细节的情况下，我建议您查看解释器的文档。

于 2013-02-22T22:38:44.600 回答
1

使非法移动标志成为函数中的参数而不是全局变量

我会给你一个带有阶乘的简单例子

即：0！= 1个！= n * (n - 1)！当 n (1 ... 无穷大)

让我们称之为递归阶乘

(define (fact-r n)
    (if 
       [eq? n 0] 
       1 
       (* n (fact-r (- n 1)))
    )
)

另一种方法是使用函数的参数来结束递归让我们称之为迭代阶乘

(define (fact-i n total)
  (if 
      (eq? n 0) 
      total
      (fact-i (- n 1) (* n total))
  )
)

total 需要从 1 开始，所以我们应该创建另一个函数以更好地使用它

(define (nice-fact n)
  (fact-i n 1))

你可以用非法移动标志做类似的事情来避免使用全局变量至于避免使用集合！去，我们可能需要更多信息。

在某些情况下，仍然很难避免使用它。无需使用 set，Scheme 就是完全图灵完备的！但是，在访问外部信息源（例如数据库或机器人集）时！可以成为唯一可行的解​​决方案...

于 2013-02-24T10:54:54.627 回答