Spake Eben King on Friday, July 07, 2006 at 01:14PM -0400:
> The prof said any recursive algorithm can be turned into a non-recursive
> algorithm, which is reasonable, as that's what compiled code with loops
> completely unrolled is.
This is somewhat misleading.
Any recursive function can be written using iteration, however this does
not always result in faster code.
The problem with recursive functions is not the recursion itself, but
the stack space used by each call.
Take the function "sum" function, which recursively performs addition on
a list of integers:
let rec sum list =
match list with
[] ->
(* return 0 for empty lists *)
0
| x :: rest ->
(* return first item + sum of rest of list. *)
x + sum rest
This function is written in ocaml, and is not tail recursive. For each
item in list, some stack space is used in a call to sum(). This is
pretty bad, as you're going to run out of stack space eventually, and
the program will abort (actually, in ocaml an exception is raised, but
that is becides the point).
We can write this with tail recursion:
let rec sum_tail total list =
match list with
[] -> total
| x :: rest -> sum_tail (x + total) rest
It is obvious that the last thing the function
does is call itself, and thus (with compiler magic) this is as efficient
as an iterative version (that is, it doesn't use any more stack space).
Note this sum_tail function must be called as: sum_tail 0 list.
Typically you'd define the function like this, and create a wrapper
function:
let sum list = sum_tail 0 list
--
"If there is not love in your heart, so sorry,
then there will never be hope for you."
-- David "Ziggy" Marley, "Tomorrow People" (song)
-
GPG Fingerprint: E3CD FDAB 82C4 14FD 7B57 430B 770E 0EAF FB53 12C2
-----------------------------------------------------------------------
This list is provided as an unmoderated internet service by Networked
Knowledge Systems (NKS). Views and opinions expressed in messages
posted are those of the author and do not necessarily reflect the
official policy or position of NKS or any of its employees.
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 20:37:43 EDT