fact的尾递归化
非尾递归的fact定义
(define fact
(lambda (x)
(if (= x 1)
1
(* x (fact (- x 1))))))
尾递归的fact-tail定义
(define fact-tail
(lambda (x k)
(if (= x 1)
(k 1)
(fact-tail (- x 1)
(lambda (y) (k (* y x)))))))
分析调用过程
(fact-tail 3
(lambda(n) n))
<=>
(fact-tail 2
(lambda (y) (
(lambda(n) n)
(* y 3)
)))
<=>
(fact-tail 1
(lambda (y) (
(lambda (z) (
(lambda(n) n)
(* z 3)
))
(* y 2)
)))
<=>
(
(lambda (y) (
(lambda (z) (
(lambda(n) n)
(* z 3)
))
(* y 2)
))
1
)
<=>
(
(lambda (z) (
(lambda(n) n)
(* z 3)
))
(* 1 2)
)
<=>
(
(lambda(n) n)
(* (* 1 2) 3)
)
<=>
(* (* 1 2) 3)
fib的尾递归化
非尾递归的fib定义
(define fib
(lambda (n)
(if (<= n 2)
1
(+ (fib (- n 1))
(fib (- n 2))))))
尾递归的fib-tail定义
(define fib-tail
(lambda (n k)
(if (<= n 2)
(k 1)
(fib-tail (- n 1)
(lambda (x)
(fact-tail (- n 2)
(lambda (y)
(k (+ x y)))))))))
分析调用过程
(fib-tail 3
(lambda (z) z))
<=>
(fib-tail 2
(lambda (x)
(fact-tail 1
(lambda (y)
(
(lambda (z) z)
(+ x y)
)))))
<=>
(
(lambda (x)
(fact-tail 1
(lambda (y)
(
(lambda (z) z)
(+ x y)
))))
1
)
<=>
(fact-tail 1
(lambda (y)
(
(lambda (z) z)
(+ 1 y)
)))
<=>
(
(lambda (y)
(
(lambda (z) z)
(+ 1 y)
))
1
)
<=>
(
(lambda (z) z)
(+ 1 1)
)
<=>
(+ 1 1)