Tail recursion with Scheme. Decoding trees

Question

I am not sure about the difference between tail recursion and general recursion. How is the code below "decode" not tail recursive, and how can I make it tail recursive?

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
    (let ((next-branch
      (choose-branch (car bits) current-branch)))
        (if (leaf? next-branch)
          (cons (symbol-leaf next-branch)
            (decode-1 (cdr bits) tree))
         (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

What am I doing wrong in my code below (for the tail recursive procedure)?

(define (decode2 bits tree)
  (define (decode-1 bits current-branch res)
     (if (null? bits)
       (reverse res)
       (let ((next-branch
            (choose-branch (car bits) current-branch)))
            (if (leaf? next-branch)
                (decode-1 (cdr bits) tree (cons (symbol-leaf next branch) res))
                (decode-1 (cdr bits) tree res)))))
      (decode-1 '() tree res))

coredump · Accepted Answer · 2021-10-06T08:45:33.713

In the code below, you are using the result of (decode-1 ...) as an argument to cons:

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))  ;; << here
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

The result of the current level of recursion is not directly computed by a function call (here a recursive call), but combines this result with another value to build a result.

This means that the runtime has to keep track of the local state of computation (called a frame) while computing the recursive call to decode-1, in order to be able to build the resulting list with cons. This makes all the recursive calls wait one for another, acting like a stack.

With a recursive terminal function, you can discard all the state of your current call before calling yourself recursively: there should be no necessary state to keep for when the recursive call return: this is the condition that allows an interpreter (or compiler) to replace the call by a jump (this need not be a recursive call, tail call elimination may happen for any function).

You can add an additional parameter to decode-1 (often called "an accumulator"), here the list you want to return. For example, you can call it res for result. Initially it is the empty list.

When you reach (null? bits), you return the list computed so far, res. The list is probably going to be in reverse order, so you may want to reverse it (this can be made recursive terminal too).

In the general case of recursion, you call:

(decode-1 (cdr bits)
          tree 
          (cons (symbol-leaf next-branch) res))

In other words, you first build a list, compute (cdr bits), etc (in no particular order theoretically), then you pass all the three values to decode-1: when this call returns, it will exactly be the return value you want to topmost call to return, so there is no need to track any other variable in the function.

Morten Jensen · Answer 2 · 2021-10-06T14:59:57.923

Tail recursion is when the recursive call is the last thing that happens - i.e. when the recursive call is in "the tail position".

As coredump explains in his answer, a function is tail-recursive if there is nothing left to do after the recursive call.

The reason to care about tail-recursion, is that it can be implemented more efficiently than "regular" recursion.

If nothing needs to be done after recursion, the recursive call can be replaced with a "jump to the top of the function". That means you avoid the function call and the associated call-stack.

An often-used pattern for converting to tail-recursion, is to add an accumulator-argument to the function to hold the intermediate result explicitly (instead of using the call-stack for it implicitly).

Here is an example of the factorial function implemented with regular recursion, and tail recursion.

Regular recursion:

(define (fact n)
        (if (= n 0) 1
            (* n (fact (- n 1)))))

With tail-recursion + accumulator (acc):

(define (fact-tail n)
        (define (fact-helper n acc)
                (if (= n 0) acc
                    (fact-helper (- n 1) (* acc n))))
        (fact-helper n 1))

FWIW Some people differentiate "recursion" and "iteration" in context of functional programming, and mean tail-recursion when they talk about "iteration".

See these links for another introduction to the concept:

So, is it correct that a tail-recursive procedure is an iterative process? — N.A., Oct 06 '21 at 17:04
@N.A. It quickly degenerates into a discussion of semantics. What is iteration? E.g. in Scheme you have no `for` or `while`-loops so recursion is used for iteration but in C/C++ you would not equate iteration with recursion at all ¯\_(ツ)_/¯ However it is a somewhat common convention in older FP-literature in my experience. — Morten Jensen, Oct 06 '21 at 17:55

Tail recursion with Scheme. Decoding trees

2 Answers2