使用CPS将fact和fib改为tail recursion

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)