recursion - 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.