0

我必须在Scheme（R5RS）中创建一个函数，其工作方式如下：（power-close-to bn）它必须返回一个我称之为“e”的整数：b^e > n With b, e and n 个整数。

所以如果我们这样做：(power-close-to 2 10) 它必须返回 4，因为 4 是 b^e > n 的第一个整数，我以迭代的方式制作了这个函数，但我必须让它一种递归形式。所以这是我的代码：

(define e 0)
(define (power-close-to b n)
  (for ((e (< (expt b e) n))
    (+ e 1))
    e))

但是当我尝试它时，Scheme 给出了以下错误：“for: undefined;” 所以看来我的Scheme不知道“for”的过程，但我在互联网上的多个Scheme代码中看到了它，所以我不明白为什么在我的情况下他说他不知道“for”。

谢谢你的帮助！

编辑：我试着让它递归，我就是这样做的，但我认为它仍然是迭代的，我真的不知道如何让它递归。

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (and (set! e (+ e 1)) (power-close-to b n)) 
    e))

我也试过这个，但是当我尝试它时，它永远不会打印任何东西并且永远不会结束（但这是递归的（我认为））

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (* b (power-close-to b n)) 
    e))
4

2 回答 2

2

当有人要求您将 Scheme 中的递归过程转换为迭代过程时，通常意味着您必须使用尾递归，而不是您应该使用语言的循环结构。

请注意，并非所有 Scheme 解释器都提供for循环（大多数会提供do循环，但我认为这不是练习的重点）。您报告的错误意味着您的解释器没有for构造，因此您很可能希望以尾递归方式重写该过程。我会给你一个例子来说明我的意思，这是一个递归阶乘：

(define (fac n)
  (if (zero? n)
      1
      (* n (fac (sub1 n)))))

(fac 10)
=> 3628800

现在可以用这样的方式编写相同的过程，它会生成一个迭代过程（即使在语法上，它仍然使用递归）：

(define (fac n acc) ; now the result is stored in the accumulator parameter
  (if (zero? n)     ; when recursion ends
      acc           ; return accumulator
      (fac (sub1 n) (* n acc)))) ; else update accumulator in each iteration

(fac 10 1) ; initialize the accumulator in the right value
=> 3628800

你问有什么意义？该过程的第二个版本是以尾递归形式编写的（请注意，在递归调用结束后没有什么可做的），所以一个称为尾调用优化的编译器技巧开始起作用，并且该过程在恒定堆栈空间中运行，就像在其他非函数式语言中作为循环高效 - 使递归调用非常便宜。现在尝试编写您的power-close-to实现，以便它使用尾调用。

于 2013-10-04T16:45:00.777 回答
0

与传统循环最接近（也是最方便）的是命名的let（在此处搜索“命名的let” ）。看起来像这样：

(define (power-close-to b n)
  (let loop ((e 0))
    (if (<= (expt b e) n)
        (loop (+ e 1))
        e)))

(display (power-close-to 2 10))

循环变量是在 let 级别定义的，因此它是循环的本地变量（在您的示例中不是全局变量）。除此之外，代码看起来与您的非常相似。

命名的 let 创建了一个内部函数，因此您也可以将其表示如下：

(define (power-close-to b n)

  (define (loop e)
    (if (<= (expt b e) n)
        (loop (+ e 1))
        e))

  (loop 0))

不幸的是，R5RS 不支持参数的默认值，但如果你想避免使用内部函数，你可以选择：

(define (power-close-to b n e)
  (if (<= (expt b e) n)
      (power-close-to b n (+ e 1))
      e))

但是你必须用额外的 0 来调用它

(power-close-to 2 10 0)
于 2013-10-04T20:01:25.410 回答