Factorial without recursion or iteration (or how TC can be fun)!

Home | Archive

Factorial without recursion or iteration (or how TC can be fun)!

2006-01-09T09:00:00

TC = Theory of Computation In the beginning, you thought you couldn't do without iteration. Then you realized that you can do away with iteration and do stuff recursively. Then came the realization that what you call `iteration' is just another form of `tail recursion' (Lisp guys love to call it mere `syntactic sugar') The power of the computer is in doing things repeatedly, and for this, we use recursion. A function calling itself is called `recursion'. But can a function call itself without calling itself? Well? For a function to call itself, it needs a name. In Scheme, you can create nameless functions using `Lambda':

(lambda (x) (* x x))

is an `anonymous' function which accepts an argument and returns its square. You can do stuff like:

((lambda (x) (* x x)) 2)

you are now `applying' this function on the number 2. Now note that this function can't call itself, becuase it doesn't have a name. But then we have closures:

(lambda (a) (lambda (b) (+ a b)))

The first anonymous functions accepts one argument `a' and returns a function which itself takes one argument and sums it up with `a'. That is, you can do stuff like:

(display (((lambda (a) (lambda (b) (+ a b))) 2) 3))

Once we reach this far, its possible to do a really cool trick and have a nameless function call itself. Read more about it here: Many faces of the fixed point combinator Alonzo Church's Lambda Calculus forms the basis of the manipulations we did - it's usually taught in Theory of Computation classes, and most people hate it. But with a bit of effort, it can be made interesting even to those students who are not very comfortable with abstract thought. I have a small LG document which explores a bit more of lambda (in Python) - read it here

---

kesavan

Fri Oct 10 12:58:48 2008

this cannot be done with a c program!!!!