scheme - Is function tail-recursive?

Question

I have implemented this recursive function in scheme:

       (define f (lambda (n)

        (cond ((= n 0) 0)
              ((= n 1) 2)
              ((= n 2) 37)
              ((odd? n) (+ (f (- n 3)) 1))
              (else (+ (f (- (/ n 2) 1)) 7))))
        )

On a lot of exercises I have been asked wether my solution is tail recursive or not and to be honest, no matter how many times i read the definition of tail recursion, I just don't understand it. If I would define tail-recursive, it would be something like this.

Definition: A tail-reursive function is calculated in a constant memory space no matter the input value.

Here's also another two. One of them is tail-recursive and i want to find out which one.

(define ln2-a
 (lambda (n)
 (define loop
   (lambda (n)
     (if (= n 1)
         0
        (+ 1 (loop (quotient n 2))))))
 (trace loop)
 (loop n)))

And here.

(define ln2-b
  (lambda (n)
    (define loop
      (lambda (n result)
      (if (= n 1)
         result
       (loop (quotient n 2) (+ result 1)))))
 (trace loop)
 (loop n 0)))

Let's take a look at the two last functions. Here I suppose ln2-b is the recursive one. But I can't really answer why, which kinda irritates me. I think trace loop helps me BUT I am not quite sure what it says and how it helps me. I try to compare all three functions find similarities but also how they differ from each other. But, unfortunately, I can't manage to do it...

Hope someone friendly can help me, thanks. Oh and I am also really new to computer science so perhaps I use some terminology wrong. If something is unclear, just say it. :)

Answer 1

It's very simple.. When you need to do something with the result of the recursion it's not tail recursive.

(define (length lst)
  (if (null? lst)
      0
      (+ 1
         (length (cdr lst))))

Here you clearly see we have to + 1 to the answer from the recursion. This happens in every step so the stack builds up until the base case hit and we add 1 for each element on out way back. (length '(1 2 3 4)) ; ==> (+ 1 (+ 1 (+ 1 (+ 1 0))))

When the procedure is finished and the result is the result of the last step (base case) it is tail recursive.

(define (length lst)
  (define (aux lst count)
    (if (null? lst)
        count ; last step
        (aux (cdr lst) (+ 1 count))))

  (aux lst 0))

Here the helper procedure has count as an argument and instead of having to wait to add 1 you do it before the recursion happens (by increasing the argument). The result of the whole thing is just the result of the base case and nothing more. It is tail recursive. Even the call to the helper is a tail call, but not recursive, but all tail calls are optimized in Scheme.

Now, which of your two procedures are tail recursive?

Answer 2

In your first code block, f is not tail recursive. The recursive call to f has to happen, return its result, and then 1 or 7, depending on the branch, has to be added to the result. Since the call to recursive call to f has to return, and there are arbitrarily many recursive calls to f, this means that arbitrarily many stack frames must be allocated.

When you think of calling a function, it may help to imagine that you take a new piece of paper and write all the of the local variables and values on that piece of paper. When you're determining the result of the function, there may be recursive calls to the same function. If the call is a tail-call, then when you take a piece of paper for it, you can throw away the old sheet, since you don't need any of its values anymore.

For instance, consider two ways of computing the length of a list:

(define (length-1 list)
  (if (null? list)
      0
      (+ 1
         (length-1 (cdr list))))) ; recursive call, NOT a tail-call

In this implementation, you have to finish the recursive call to length-1, get its result, and add 1 to it. That means that you need somewhere to come back to after the recursive call. Now consider a tail-recursive version:

(define (length-2 list current-length)
  (if (null? list)
      current-length
      (length-2 (cdr list) ; recursive call, IS a tail-call
                (+ 1 current-length))))

In this version, once you start to make the recursive call to length-2, you don't need any context from the original call anymore. In fact, you could translate this to a loop by assigning (cdr list) to list, and assigning (+ 1 current-length) to current-length. You can reuse the same stack space. That's how tail call optimization (when the tail call is to the same function) is equivalent to a loop.

Answer 3

The tail recursive function will pass the accumulated result into each call, so that once the end condition is reached, the result can be immediately returned by that last call of the function.

A non-tail recursive function will require something be done to the result after it has been returned. So, each layer of recursion has to be remembered so that it can work its way back out to calculate the final result.

In your first example, you are adding to the result of the next call of f, so it is not tail recursive.

The second example is also adding to the next call of loop, so it is not tail recursive.

The third example, passes the final result in as an argument into the next function call, so it is tail recursive.