scheme - 递归指数函数的迭代版本

Question

我基本上需要对我已经制作的以下函数进行迭代版本：

(define (expo base e)
  (cond ((or (= base 1) (= e 0)) 1)
        (else (* base (expo base (- e 1))))))

我不知道怎么做，所以我需要帮助（在球拍/计划中））

Answer 1

您所要做的就是将结果传递到一个累加器中。为此，您需要一个额外的参数，有几种方法可以做到这一点，例如使用内部帮助程序：

(define (expo base e)
  ; helper procedure
  (define (iter e acc)
          ; now the base case returns the accumulator
    (cond ((or (= base 1) (= e 0)) acc) 
          ; see how the result is accumulated in the parameter
          (else (iter (- e 1) (* base acc)))))
  ; at the beginning, initialize the parameter in the right values
  (iter e 1))

或者，我们可以使用命名let来实现相同的效果：

(define (expo base e)
  (let iter ((e e) (acc 1))
    (cond ((or (= base 1) (= e 0)) acc)
          (else (iter (- e 1) (* base acc))))))

区分递归过程和过程是很好的。上述两种实现都是递归过程：从句法上看，很容易看出它们是自称的。但是它们生成的过程是迭代的：它们是用尾递归风格编写的，所以在每次递归调用结束后就没有什么可做的了，编译器可以优化掉递归调用，并且出于所有实际目的，将其转换为迭代循环。

为了更好地理解 Scheme 中的迭代是如何工作的，请阅读精彩的SICP书中有关此主题的更多信息，在程序和它们生成的过程部分

Answer 2

将此类递归函数转换为迭代的一般模式是使用累加器

(define (expo base e)
   (define (go base e accum)
      (if (or (= base 1) (= e 0))
          accum
          (go base (- e 1) (* accum base)))) ; Now this is tail recursion
    ???)

Where???调用go具有适当的初始值accum. 请注意，recusive 调用之前是如何在另一个调用（即*）中的，但现在它是最后调用的东西。这允许程序在恒定空间中运行。

Answer 3

正如其他人所指出的，尾递归算法是一种迭代算法。但是，也许您需要一个显式的迭代算法？

(define (expo base exp)
  (do ((acc   1 (* acc base))
       (exp exp (- exp 1)))
      ((= 0 exp) acc))))

可以添加一个条件(= base 1)- 但是，正如所写，这是一个简单的事情。假设exp是一个整数。