做备忘用.
上代码

#lang racket

;;factorial 
;;non-tail recursion

(define (fact1 n)
  (if (= 0 n)
      1
      (* n (fact1 (- n 1)))))

;;factorial
;;tail recursion
(define (fact-aux n result)
  (if (= 0 n)
      result
      (fact-aux (- n 1)(* n result))))

(define (fact2 n)
  (fact-aux n 1))

(define (fact3 n)
  (let fact-aux ([s n][result 1])
    (if (= 0 s)
        result
        (fact-aux (- s 1)(* s result)))))


;;fibonacci
;;non-tail recursion
(define (fib1 n)
  (if (< n 2)
      n
      (+ (fib1 (- n 1))(fib1 (- n 2)))))

;;fibonacci 
;; tail recursion

(define (fib-aux n next result)
  (if (= n 0)
      result
      (fib-aux (- n 1) (+ next result) next)))

(define (fib2 n)
  (fib-aux n 1 0))

(define (fib3 n)
  (define (fib-aux n next result)
    (if (= 0 n)
        result
      (fib-aux (- n 1) (+ next result) next)))
  (fib-aux n 1 0))

when converting recursive functions to tail  recursive funcion.add a auxiliary parameter.

ps. python 没有尾递归优化.
lisp系有.解释器自动将尾递归转化为迭代.

参考:

http://www.csee.umbc.edu/~chang/cs202.f98/readings/recursion.html

• 相关文章
• 全局相关文章