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

Question

你能否将每个具有递归过程的递归过程从递归（甚至树递归）转变为迭代，反之亦然（在 Scheme 中）？通过改变代码的编写方式？

Answer 1

是的，绝对是。递归函数总是有一个中断条件。有时中断条件是关于一个 used-up 的列表，因此从递归调用到下一个递归调用变为空。在这种情况下，您可以通过列表上的 for-loop 来处理它。有时中断条件是一些数字减少或其他 - 然后可以使用 while 循环来测试中断条件。

Answer 2

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

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

但是，某些算法可能会被执行其他操作的其他算法所取代。斐波那契程序就是一个很好的例子。这是一个树步行版本：

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

您可能已经看到了这个版本，其算法只是迭代 window 从底部到答案的值：

(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 几乎相同，除了它使用操作列表和参数堆栈。这是一个递归过程，但过程是尾递归的，因此是迭代的。

如果不更改算法，则无法将继承迭代过程转换为递归过程。将其视为具有 fib-iter 并将其重写为 fib-rec。此外，由于 Scheme 除了递归之外没有原始循环结构，所以所有迭代过程都是通过递归完成的。如果您阅读报告，您会看到 do 和其他循环结构是派生语法以及它们变成的递归。

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

Every procedure from recursive to iterative and vice versa?

lisp

scheme

racket