In Scheme, how do you use lambda to create a recursive function?

Question

I'm in a Scheme class and I was curious about writing a recursive function without using define. The main problem, of course, is that you cannot call a function within itself if it doesn't have a name.

I did find this example: It's a factorial generator using only lambda.

((lambda (x) (x x))  (lambda (fact-gen)    (lambda (n)      (if (zero? n)          1          (* n ((fact-gen fact-gen) (sub1 n))))))) 

But I can't even make sense of the first call, (lambda (x) (x x)): What exactly does that do? And where do you input the value you want to get the factorial of?

This is not for the class, this is just out of curiosity.

Answer 1

(lambda (x) (x x)) is a function that calls an argument, x, on itself.

The whole block of code you posted results in a function of one argument. You could call it like this:

(((lambda (x) (x x))   (lambda (fact-gen)     (lambda (n)       (if (zero? n)           1           (* n ((fact-gen fact-gen) (sub1 n)))))))  5) 

That calls it with 5, and returns 120.

The easiest way to think about this at a high level is that the first function, (lambda (x) (x x)), is giving x a reference to itself so now x can refer to itself, and hence recurse.

Answer 2

The expression (lambda (x) (x x)) creates a function that, when evaluated with one argument (which must be a function), applies that function with itself as an argument.

Your given expression evaluates to a function that takes one numeric argument and returns the factorial of that argument. To try it:

(let ((factorial ((lambda (x) (x x))                   (lambda (fact-gen)                     (lambda (n)                       (if (zero? n)                           1                           (* n ((fact-gen fact-gen) (sub1 n)))))))))   (display (factorial 5))) 

There are several layers in your example, it's worthwhile to work through step by step and carefully examine what each does.