​Relations between recursion, stacks, and queues

For the sake of discussion, let’s consider a recursive and an iterative function that converts a number to a list.

(define (number->list l)
  (if (= l 0)
      '()
      (cons
       (remainder l 10)
       (number->list (quotient l 10)))))

(define (number->list-iter l acc)
  (if (= l 0)
      acc
      (number->list-iter
       (quotient l 10)
       (cons (remainder l 10) acc))))

Calling the functions produce:

> (number->list 123)
'(3 2 1)
> (number->list-iter 123 '())
'(1 2 3)

Further, let’s consider this same function rewritten in JavaScript, but implemented with stacks and queues instead of recursion:

function numbertolist_stack(n) {
        var stack = [n];

        while (stack.length) {
                var x = stack.pop();
		stack.push(x % 10);

                if (parseInt(x / 10)) {
                        stack.push(parseInt(x / 10));
                } else {
                        break;
                }
        }

        return stack;
}

function numbertolist_queue(n) {
        var queue = [n];

        while (queue.length) {
		var flag = false;
                var x = queue.shift();

                if (parseInt(x / 10)) {
                        queue.push(parseInt(x / 10));
		} else {
			flag = true;
		}

		queue.push(x % 10);

                if (flag) {
                        break;
                }
        }

        return queue;
}

So, now we have:

> numbertolist_stack(123)
[ 3, 2, 1 ]
> numbertolist_queue(123)
[ 1, 2, 3 ]

So, in terms of cons, what we can conclude is that recursion can be viewed as a stack, and tail recursion can be viewed as a queue. For if we haven’t worked in terms of cons, we can rewrite the Scheme iter function to use (append acc (list (remainder l 10))) instead of cons and achieve the same effect as number->list.

However, note that most interpreters that contain an implementation of tail call optimization wouldn’t probably implement a queue, but only a fixed set of variables in order to save space.

Another interesting observation is that we can look at it in terms of associativity (think foldr and foldl). foldr is implemented using a stack, and foldl is implemented using a queue, so that gives an idea in terms of associativity.

Or that we can implement depth-first search with a stack and breadth-first search with a queue.

IMHO, discovering relations like this is fun 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s