如何使 tribonacci 函数尾递归？

Question

我正在制作一个 tribonacci 函数，给定 n，returns 值，n(0)=0，n(1)=0，n(2)=1。
我当前的代码只是正常的递归，但我怎样才能使它成为尾递归呢？

(define (tribonacci n)
 (if ( < n 0) #f
  (cond ((= n 0) 0)
        ((= n 1) 0)
        ((= n 2) 1)
        ((> n 0)
          (+ (tribonacci (- n 1)) (+ (tribonacci (- n 2))(tribonacci (- n 3))))))))

Answer 1

任何使用前面的一些答案来计算下一个答案的递归函数都可以通过将变量的数量保持为基本情况来进行迭代。在普通 fibonacci 的情况下，您有两个基本情况，下一个值始终是前两个

的总和

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

所以假设您想要 (fib 4) 它执行这些迭代：

注意a实际上是从头开始的所有斐波那契数，而b是从第二个值开始的所有斐波那契数，我们比我们需要的结果多计算一个。另一种看待它的方式是，变量就像一个 window 在斐波那契数字上移动。

我会让你对你的特殊版本做同样的事情，因为它可以用迭代循环中的第三个变量以完全相同的方式解决。祝你好运！

Answer 2

这是一个使用尾递归函数的版本。

(define (tribonacci n)
  (define (helper n a b c)
    (format #t "a: ~a, b: ~a, c: ~a\n" a b c)
    (if (= n 0)
      a
      (helper (- n 1) b c (+ a b c))))

  (if ( < n 0) #f
    (helper n 0 0 1)))

执行(tribonacci 10)的输出：

a: 0, b: 0, c: 1
a: 0, b: 1, c: 1
a: 1, b: 1, c: 2
a: 1, b: 2, c: 4
a: 2, b: 4, c: 7
a: 4, b: 7, c: 13
a: 7, b: 13, c: 24
a: 13, b: 24, c: 44
a: 24, b: 44, c: 81
a: 44, b: 81, c: 149
a: 81, b: 149, c: 274

如何使 tribonacci 函数尾递归？

How to make tribonacci function tail recursive?

scheme

racket

r5rs