CODEWITHSUNDEEP
schemelispracket
user7120460
user7120460

Reputation:

Is this procedure recursive or iterative (long tail recursion)?

The following code is used to implement a built-in function called "build-list":

(define (my-build-list-book n f)
 (define (builder k)
   (cond [(= n k) empty]
         [else (cons (f k) (builder (add1 k)))]))
  (builder 0))

(my-build-list-book 10 add1)
>> '(1 2 3 4 5 6 7 8 9 10)

Is this a recursive definition of an iterative procedure or a recursive definition of a recursive procedure?

Upvotes: 0

Views: 67

Answers (1)

Barmar
Barmar

Reputation: 781300

builder is recursive because it calls itself: (builder (add1 k))

It's not tail recursive because the call to itself is not done in the place where a value is returned from the original procedure. It uses the result of the recursive call as an argument to cons rather than as the return value.

A tail-recursive variant would end with something like:

[else (builder ...)]

Converting a function like this to tail-recursion generally requires adding an additional argument that contains the accumulated result, which is returned by the base case.

(define (my-build-list-book n f)
  (define (builder k result)
    (cond [(= n k) result]
          [else (builder (add1 k) (cons (f k) result))]))
  (builder 0 '()))

I'm not sure what you mean by "long tail recursion", I've never heard that phrase and I can't find it with Google.

Upvotes: 1

Related Questions