next up previous contents index
Next: Example of Step by Up: Using the Y-Combinator to Previous: Introduction   Contents   Start

Steps to Eliminate Implicit Recursion

  1. recursive function to calculate the factorial including illegal implicit recursion:

    $ FAC = \lambda n.(IF (= n\hspace{0.25em} 0) 1 (* n (FAC (- n\hspace{0.25em} 1))))$

  2. locating illegal implicit recursion:

    $ FAC = \lambda n.(... FAC ...)$

  3. eliminating illegal implicit recursion:

    $ FAC = (\lambda fac. \lambda n.( \dots fac \dots) FAC)$

  4. simplified representation:

    $ FAC = (M\hspace{0.25em} FAC)$

    where:

    $ M = \lambda fac. \lambda n.(... fac ...)$

    The recursion is eliminated by enclosing the recursive function in a lambda abstraction, that receives the function to be invoked recursively as an argument.

  5. Using definition 12 and the result in step 4 $ FAC$ is identified as a fixed point of $ M$.

    Therefore we can write:

    $ FAC = (Y\hspace{0.25em} M)$

  6. The function to calculate the factorial can now be rewritten as:

    $ FAC = (Y \hspace{0.25em}\lambda fac. \lambda n.(... fac ...)) $

  7. To compute the factorial of $ n$ the following expression has to be evaluated:

    (( $ Y\hspace{0.25em} \lambda fac. \lambda n.(... fac ...)\hspace{0.25em}) n) $



Georg P. Loczewski 2004-03-05


Impressum und Datenschutz