CODEWITHSUNDEEP
recursionlambdaschemesicp
18bytes
18bytes

Reputation: 6029

Scheme: How do we write recursive procedure with lambda?

I was going through Structure and interpretation of computer programming by Brain harvey. I came across this question which i could not figure out how to do it.

How do we write recursive procedure with lambda in Scheme?

Upvotes: 1

Views: 4754

Answers (3)

paul
paul

Reputation: 1150

No need to write factorial body twice ;)

(((lambda (f)
   (lambda (x)
     (f f x)))
 (lambda (fact x)
   (if (= x 0) 1 (* x (fact fact (- x 1)))))) 5)

Upvotes: 5

Rajesh Bhat
Rajesh Bhat

Reputation: 1000

Here is a recursive function that calculates the factorial of 5 using lambda

((lambda (f x)
  (if (= x 0)
      1
      (* x (f f (- x 1)))))
 (lambda (f x)
  (if (= x 0)
      1
      (* x (f f (- x 1)))))
 5)

When you run this program in Drracket you get 120 :)

Upvotes: 2

C. K. Young
C. K. Young

Reputation: 223003

TL;DR: Use named let (if you are executing a recursive function immediately) or rec (if you are saving the recursive function for later execution).

The usual way is with letrec, or something that uses a letrec behind the scenes, like named let or rec. Here's a version of (factorial 10) using letrec:

(letrec ((factorial (lambda (x)
                      (if (< x 1) 1
                          (* (factorial (- x 1)) x)))))
  (factorial 10))

And the same thing using named let:

(let factorial ((x 10))
  (if (< x 1) 1
      (* (factorial (- x 1)) x)))

The key understanding here is that both versions are exactly the same. A named let is just a macro that expands to the letrec form. So because the named let version is shorter, that is usually the preferred way to write a recursive function.

Now, you might ask, what if you want to return the recursive function object directly, rather than execute it? There, too, you can use letrec:

(letrec ((factorial (lambda (x)
                      (if (< x 1) 1
                          (* (factorial (- x 1)) x)))))
  factorial)

There, too, is a shorthand for this, although not using named let, but instead using rec:

(rec (factorial x)
  (if (< x 1) 1
      (* (factorial (- x 1)) x)))

The nice thing about using rec here is that you can assign the function object to a variable and execute it later.

(define my-fact (rec (factorial x)
                  (if (< x 1) 1
                      (* (factorial (- x 1)) x))))
(my-fact 10)  ; => 3628800

The more theoretical and "pure" way to create recursive functions is to use a Y combinator. :-) But most practical Scheme programs do not use this approach, so I won't discuss it further.

Upvotes: 9

Related Questions