Can anyone tell me how to use lambda to do recursion?

Colleges & Universities University of California - Berkeley
1

<p>Can anyone tell me how to use lambda to do recursion? It is last week’s homework. However, I can’t find the solution in newsgroup.</p>

2

<p>The idea is that a function has to know about itself and the only way to do THAT is to pass itself to itself. It’s a mindbender, but it’s an extra for experts so don’t worry too much about it.</p>

3

<p>You have to use lambdas inside of lambdas. Look up Y-combinator.</p>

4

<p>If you’re wondering, no the exams will not contain questions of that difficulty. In fact, the homework is HARDER than the exams. Take a look at the practice problems if you don’t believe me ;)</p>

5

<p>Doesn’t seem like it’s relevant whether or not this guy wants to get a grade. Considering it’s last week’s homework, it seems like that he wants to learn.</p>

<p>I just looked at the solutions a few hours ago, and surely enough, the answer is there. The idea is to use the function that is generated by a function that calls a function it takes as a parameter, with that function being itself. Hence, the Y-combinator.</p>

6

<p>Don’t worry about not getting “extra for experts” questions. They’re beyond the level of CS61A. But if you’re just curious, here’s how to write factorial with lambda, using the Y-combinator trick. The whole expression below is a procedure that takes in a number as argument and returns its factorial.</p>

<p>(lambda (x)
((lambda (f n) (f f n)) ;;<–This procedure here is the Y-combinator
(lambda (fact n)
(if (= n 0)
1
(* n (fact fact (- n 1)))))
x))</p>

<p>In the future, such questions should be posted on the newsgroup, so that they’re more likely to be answered.</p>