尾递归改写为递归
做备忘用.
上代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #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
评论 (0)
