Scheme中的尾递归函数 [英] Tail recursive functions in Scheme

问题描述

我正在为圣诞节考试而学习并做一些样题，我遇到了这个让我有点困惑的问题

I'm studying for a Christmas test and doing some sample exam questions, I've come across this one that has me a bit stumped

我可以很好地进行常规递归，但我无法思考如何使用尾递归编写相同的内容.

I can do regular recursion fine, but I can't wrap my head around how to write the same thing using tail recursion.

普通版:

    (define (factorial X)
      (cond
            ((eqv? X 1) 1)
            ((number? X)(* X (factorial (- X 1))))))

推荐答案

对于尾递归的函数来说，函数返回后除了返回它的值之外，必须什么都不做.也就是说，递归步骤中发生的最后一件事是对函数本身的调用.这通常是通过使用累加器参数来跟踪答案来实现的:

For a function to be tail recursive, there must be nothing to do after the function returns except return its value. That is, the last thing that happens in the recursive step is the call to the function itself. This is generally achieved by using an accumulator parameter for keeping track of the answer:

(define (factorial x acc)
  (if (zero? x)
      acc
      (factorial (sub1 x) (* x acc))))

上面的过程最初会以 1 作为累加器被调用，就像这样:

The above procedure will be initially called with 1 as accumulator, like this:

(factorial 10 1)
=> 3628800

请注意，当达到基本情况时会返回累积值，并且 acc 参数在递归调用的每个点都会更新.我不得不向该过程添加一个额外的参数，但这可以通过定义一个内部过程或一个命名的 let 来避免，例如:

Notice that the accumulated value gets returned when the base case is reached, and that the acc parameter gets updated at each point in the recursive call. I had to add one extra parameter to the procedure, but this can be avoided by defining an inner procedure or a named let, for example:

(define (factorial x)
  (let loop ((x x)
             (acc 1))
    (if (zero? x)
        acc
        (loop (sub1 x) (* x acc)))))

这篇关于Scheme中的尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！