λ-wiki

λ-wiki :: tail_recursion

www!k! v.20120610

λ-wiki :: éditeur

{center {a functions} [[booleans]] [[iterations]] [[recursion]] [[tail_recursion]] [[factorial]]}

_h1 tail récursion
_p Classical recursion doesn't work but tail recursion {b does}. This is a way to play with : 
{pre °°
1) the recursive function :
    {define r_function result counter counter_max = 
      (if (greaterthen counter counter_max) 
          then result
          else (r_function (some operation on result counter) (incr counter) counter_max)
      )
   }
2) the associate calling function :
   {define recfunction counter_max = (r_function initial_result counter counter_max)}
3) calling this function :
   {recfunction N} gives the result
4) calling a incremental serie of results :
   {for :i in [:a,:b] do (recfunction :i) } gives a sequence from :a to :b
°°}
_p The name of the arguments must be prefixed by ":" ; in the future this constraint should disappear. More explanations can be found in the code's [[parser|parser.js]], around the line 805.

_h2 Some examples

_h3 1) π{sub i=1}{sup n} i (n!)

{define r_fact :p :i :n = 
   (if (greaterthen :i :n) 
       then :p
       else (r_fact (mult :p :i) (add :i 1) :n)
   )
}
{define recfact :n = (r_fact 1 1 :n)}
:n = 10 - > {for :i in [1,10] do (recfact :i) }

_h3 2) Σ{sub i=1}{sup n} i

{define r_sum :p :i :n = 
   (if (greaterthen :i :n) 
       then :p
       else (r_sum (add :p :i) (add :i 1) :n)
   )
}
{define recsum :n = (r_sum 0 1 :n)}
:n = 10 - > {for :i in [1,10] do (recsum :i) }

_h3 3) 2{sup n}

{define r_twopower :p :i :n = 
   (if (greaterthen :i :n) 
       then :p
       else (r_twopower (mult :p 2) (add :i 1) :n)
   )
}
{define rectwopower :n = (r_twopower 1 1 :n)}
:n = 10 - > {for :i in [1,10] do (rectwopower :i) }

_h3 4) Σ{sub i=0}{sup n} 2{sup -i} - > 1

{define r_sum2 :p :i :n = 
   (if (greaterthen :i :n) 
       then :p
       else (r_sum2 (add :p (quot 1 (rectwopower :i))) (add :i 1) :n)
   )
}
{define recsum2 :n = (r_sum2 0 1 :n)}  
{for :i in [1,5] do (recsum2 :i) }
- > 1 when n - > ∞

_h3 5) Σ{sub i=0}{sup ∞} {sup 1}/{sub i!} - > e

{define r_E :p :i :n = 
   (if (greaterthen :i :n) 
       then :p
       else (r_E (add :p (quot 1 (fact :i))) (add :i 1) :n)
   )
}
{define rec_E :n = (r_E 1 1 :n)}  
{for :i in [1,5] do (rec_E :i) }
- > 2.718281828459045 when n - > ∞
_h6 list of functions created
{hr}
{lib core}
{hr}
{lib dyn}