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