给定一个递归函数，如何将其更改为尾递归和流? [英] Given a recursive function, how do I change it to tail recursive and streams?

问题描述

给定方案中的递归函数，我如何将该函数更改为尾递归，然后我将如何使用流实现它?以这种方式更改任何功能时，您是否遵循了一些模式和规则?

Given a recursive function in scheme how do I change that function to tail recursive, and then how would I implement it using streams? Are there patterns and rules that you follow when changing any function in this way?

以这个函数为例，它从 2-m 中创建一个数字列表(这不是尾递归?)

Take this function as an example which creates a list of numbers from 2-m (this is not tail recursive?)

代码:

(define listupto
  (lambda (m)
    (if (= m 2)
        '(2)
        (append (listupto (- m 1)) (list m)))))

推荐答案

我将从解释您的示例开始.它绝对不是尾递归.想想这个函数是如何执行的.每次追加时，您必须先返回并进行递归调用，直到达到基本情况，然后再向上拉.

I'll start off by explaining your example. It is definitely not tail recursive. Think of how this function executes. Each time you append you must first go back and make the recursive call until you hit the base case, and then you pull your way back up.

这是你的函数的痕迹:

(listupto 4)
| (append (listupto(3)) '4)
|| (append (append (listupto(2)) '(3)) '(4))
||| (append (append '(2) '(3)) '(4))
|| (append '(2 3) '(4))
| '(2 3 4)
'(2 3 4)

注意您看到的 V 型模式，在递归调用中引入然后退出.尾递归的目标是将所有调用构建在一起，并且只执行一次.您需要做的是将累加器与您的函数一起传递，这样当您的函数达到基本情况时，您只能进行一次追加.

Notice the V-pattern you see pulling in and then out of the recursive calls. The goal of tail recursion is to build all of the calls together, and only make one execution. What you need to do is pass an accumulator along with your function, this way you can only make one append when your function reaches the base case.

这是您的函数的尾递归版本:

Here is the tail recursive version of your function:

(define listupto-tail
  (lambda (m)
     (listupto m '())))

# Now with the new accumulator parameter!
(define listupto
   (lambda (m accu)
     (if (= m 2)
        (append '(2) accu)
        (listupto (- m 1) (append (list m) accu)))))

如果我们看到这条痕迹，它看起来像这样:

If we see this trace, it will look like this:

(listupto 4)
| (listupto (3) '(4))  # m appended with the accu, which is the empty list currently
|| (listupto (2) '(3 4)) # m appended with accu, which is now a list with 4
||| (append '(2) '(3 4))
'(2 3 4)

注意模式的不同之处，我们不必遍历递归调用.这节省了我们无意义的处决.尾递归可能是一个难以掌握的概念，我建议您查看此处.第 5 章中有一些有用的部分.

Notice how the pattern is different, and we don't have to traverse back through the recursive calls. This saves us pointless executions. Tail recursion can be a difficult concept to grasp I suggest taking a look here. Chapter 5 has some helpful sections in it.

这篇关于给定一个递归函数，如何将其更改为尾递归和流?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！