4.5 Stack Frames: Implementing Recursion

Suppose that instead of concatenating the result of the recursive call to toStr with the string from convertString, we modified our algorithm to push the strings onto a stack prior to making the recursive call.

import Stack from './stack.js';

var rStack = new Stack();

function toStr(n, base) {
    var convertString = '0123456789ABCDEF';
    while (n > 0) {
        if (n < base) {
            rStack.push(convertString[n]);
        }
        else {
            rStack.push(convertString[n % base]);
        }
        n = Math.floor(n/base);
    }
    var res = '';
    while (!rStack.isEmpty()) {
        res = res + rStack.pop();
    }
    return res;
}

console.log( toStr(1453, 16) ); // 5AD

Each time we make a call to toStr, we push a character on the stack. Notice that now we can simply pop the characters off the stack and concatenate them into the final result, "1010".

The stack frames also provide a scope for the variables used by the function. Even though we are calling the same function over and over, each call creates a new scope for the variables that are local to the function.