λ-wiki

λ-wiki :: recursion

www!k! v.20120610

λ-wiki :: éditeur

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

{h1 recursion}

{div {@ float:left;} {show {@ src:http://upload.wikimedia.org/wikipedia/commons/f/f7/RecursiveTree.JPG; height:300px; width:500px;} RecursiveTree}}
_p {span {@ color:red;}Until now, recursive functions doesn't work :(}. It's a pity for a syntax which aims to be a LISP-flavoured one ! Some work is still to be done...

_p The factorial recursive function is hard-coded in the parser :  {b °°{fact 6}°° - > {fact 6}}, and there is an iterative altenative : {b °°{ifact 6}°° - > {ifact 6}}.  
_p

_h3 meanwhile ...
_p No recursion, OK, but some iteration structures work :

_h6 1) function returning 1*2*3*...*n
°°{define myfact :n = (mult (for :i in [1,:n] do :i)) }°° - > {define myfact :n = (mult (for :i in [1,:n] do :i)) }

_ul °°{myfact 10}°° - > {myfact 10}

_h6 2) function returning 1+2+3+...+n
°°{define mysum :n = (add (for :i in [1,:n] do :i)) }°° - > {define mysum :n = (add (for :i in [1,:n] do :i)) }
_ul °°{mysum 100}°° - > {mysum 100}

_h6 3) function returning 1{sup 2}+2{sup 2}+3{sup 2}+...+n{sup 2} ?
°°{define mysum2 :n = (add (for :i in [1,:n] do (mult :i :i))) }°° - > {define mysum2 :n = (add (for :i in [1,:n] do (mult :i :i))) }
_ul °°{mysum2 100}°° - > {mysum2 100}
_p {b It doesn't work} because when the expression {y (add (for :i in [1,:n] do (mult :i :i)))} is called, it is transformed in {y °°{add {for :i in [1,:n] do {mult :i :i}}}°°} (round brackets - > curly brackets). When the parser evaluates first °°{mult :i :i}°°, the counter :i is undefined at this moment and the result is NaN. 
_p Some more work to do ...

_h6 tail recursion
_p Coded in the parser static this functions work :
_ul recursive : °°{fact 10}°° - > {fact 10}
_ul iterative °°{ifact 10}°° - > {ifact 10}
_ul tail recursion : °°{tfact 10}°° - > {tfact 10}
_p Coded in the wiki page a function using the tail recursion :
{pre °°
{define myfact :p :i :n =
    (if (greaterthen :i :n) 
        then :p 
        else (myfact (mult :i :p) (add :i 1) :n) 
    )
}
°°}
{define myfact :p :i :n =
    (if (greaterthen :i :n) 
        then :p 
        else (myfact (mult :i :p) (add :i 1) :n) 
    )
} - >
{br}
°°{myfact 1 1 6}°° - > {myfact 1 1 6}  {br}... does work !

_h6 see pages [[tracing]] and [[tail_recursion]], and now it works !

_h3 lectures
{column
_h6 Recursion vs Iteration
{i posted by [[Ricky Ho|http://horicky.blogspot.fr/2008/01/recursion-vs-iteration.html]]{br}on FRIDAY, JANUARY 25, 2008}

_p Recursion is a very commonly used technique to express mathematical relationship as well as implement computer algorithm. Define a function recursively usually result in very concise form and ease the understanding. However, recursive function is not performance friendly in terms of stack growth and processing time.
_p Here is a general form of a recursive function :
{pre
def f(n)
 if (n < = j)
   return known_value[n]
 else
   return g(f(n-1), f(n-2), ... f(n-j))
}
_p When this function is invoked, the stack size will grow linearly O(n) and the processing time will grow exponentially O(j**n)
_p However, the above function can be rewritten into an iteration form. The idea is to revert the order of execution, moving from the known points to the unknown values :
{pre
def f(n)
 if (n < = j)
   return known_value[n]
 for i in 0..j
   cache[i] = known_value[i]
 for i in (j+1) .. n
   cache[i] = g(cache[i-1], cache[i-2], 
                                ... cache[i-j])
 return cache[n]
}
_p In this iteration form, the stack size will not grow and the processing time will grow linearly O(n). Therefore, performance gains significantly when the recursive form is rewrittened in the iteration form.

}