从递归到迭代的每一个过程，反之亦然

Question

你能把每个带有递归过程的递归过程从递归(甚至树递归(变成迭代，反之亦然吗(在Scheme中(？通过更改代码的编写方式？

Answer 1

您必须区分递归函数/过程和递归过程。想象一下在二叉树上行走。这肯定是一个递归过程，因为无论你如何实现它，你都需要回溯，所以如果你让它迭代，你会有某种数据结构来代替递归解决方案中使用的系统堆栈。

使用相同的算法，您无法将递归过程转换为迭代过程。这是不可能的。

然而，一些算法可能会被其他做其他事情的算法所取代。斐波那契过程就是一个很好的例子。这是一个树行走版本：

(define (fib-rec n)
  (if (< n 2)
      n
      (+ (fib-rec (- n 1)) 
         (fib-rec (- n 2)))))

您可能已经看到过这个版本，它的算法只是从下到上迭代一个值窗口，直到答案：

(define (fib-iter n)
  (let loop ((n n) (a 0) (b 1))
    (if (zero? n)
        a
        (loop (- n 1) b (+ a b)))))

这些算法不同。fib-rec的递归到迭代转换如下：

(define (fib n)
  (let loop ((jobs '(fib)) (args (list n)))
    (cond ((null? jobs)
           (car args))
          ((eq? (car jobs) 'swap)
           (loop (cdr jobs)
                 (list* (cadr args) (car args) (cddr args))))
          ((eq? (car jobs) 'add)
           (loop (cdr jobs)
                 (cons (+ (car args)
                          (cadr args))
                       (cddr args))))
          ((< (car args) 2) 
           (loop (cdr jobs) args))
          (else 
           (loop (list* 'fib 'swap 'fib 'add (cdr jobs))
                 (list* (- (car args) 2) (- (car args) 1) (cdr args)))))))

这与fib-rec几乎相同，只是它使用了一个操作列表和一个参数堆栈。这是一个递归过程，但te过程是尾部递归的，因此是迭代的。

在不改变算法的情况下，无法将继承迭代过程转换为递归过程。可以将其想象为具有fib-iter并将其重写为fib-rec。此外，由于Scheme除了递归之外没有基元循环结构，所有迭代过程都是用递归完成的。如果你阅读这些报告，你会看到do和其他循环结构是派生语法，以及它们变成了什么递归。

Answer 2

当然。递归函数总是有一个中断条件。有时，中断条件是关于一个列表，该列表已用完，因此从递归调用到下一个递归调用都变为空。在这种情况下，您可以通过列表上的for循环来处理它。有时，中断条件是关于某个数字的减少或其他什么——然后可以使用while循环来测试中断条件。