尾递归？

我正在写一个函数，它接受一个列表并返回列表中所有项目的平方和。称为上（1 2 3）它应该返回14：（1 + 2 + 3 ）。尾递归？

我有这个sqsum功能：

(define (sqsum lis) 
    (if (null? lis) 
     0 
     (+ (* (car lis) (car lis)) (sqsum (cdr lis))) 
    ) 
)

这是尾递归？我认为这是递归的，但不是尾递归。这是我家庭作业的一部分，我不在寻找解决方案：我只想知道这是否是递归的尾部递归。如果没有，那么我需要阅读更多并找到新的解决方案。

来源

2011-09-11 krunarsson

只是问自己这个函数的最后一个操作将是什么它返回之前 - 是它sqsum通话或者是+？ – Carsten

要尾递归递归具有在最后的功能的情况发生，即你不能这样做从recursiv调用的结果什么。在这里你将它传递给+，这使得它不是尾递归。尽管如此，编译器可以优化这一点，而且自己也很容易做到。

来源

2011-09-11 17:34:07 nulvinge

（定义（sqsum X）（定义（FXS）（如果（空？x）的小号（F（CDR X）（+（*（车X）（车X））S））））（FX 0））这将是尾递归？ – krunarsson

我会这么认为。 – nulvinge

另请参阅：http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 – dyoo

不，它不是尾递归。

的一般方法制备的非尾递归函数尾递归是包括一个蓄能器，它是通过您的递归调用进行的程序的当前评估一个额外的参数。

顺便说一句，这也是“助手”功能非常有用的地方。一般的做法是定义功能，使得它不采取累加器，在其中定义一个辅助函数确实采取蓄，再有主要功能不小，除了调用辅助函数。你会在一秒钟内看到我的意思。

在你的情况（如果我记得正确我的计划：P）：

(define (sqsum lis) 
    (define (sqsum-h lis acc) 
     (if (null? lis) 
      acc 
      (sqsum-h (cdr lis) (+ acc (* (car lis) (car lis)))) 
     ) 
    ) 
    (sqsum-h lis 0) 
)

这是尾递归，因为过去的事情任何递归调用不会立即返回另一个函数的结果，而无需修改它。

来源

2011-12-15 03:36:57 koschei

回答

相关问题