DS Stack Frames: Implementing Recursion

Section 4.6 Stack Frames: Implementing Recursion

Suppose that instead of concatenating the result of the recursive call to convert with the string from digitStrings, we modified our algorithm to push the strings onto a stack instead of making the recursive call. The code for this modified algorithm is shown in Listing 4.6.1.

🔗

Listing 4.6.1. Converting an Integer to a String Using a Stack

🔗

interface StackADT<T> {

// Returns true if there are no items on the stack;
    // false otherwise.
    fun isEmpty(): Boolean

// Pushes given item on the top of the stack
    fun push(item: T)

// Removes the item on top of the stack and returns it.
    // If the stack is empty, throws an exception.
    fun pop(): T

// Returns the item on top of the stack without removing it.
    // If the stack is empty, throws an exception.
    fun peek(): T

// Returns the number of items on the stack.
    fun size(): Int
}

class ListStack<T> : StackADT<T> {

/*
     * Create a new stack. The top of the stack is at the end
     * of the list.
     */
    private val items = mutableListOf<T>()

/*
     * Returns true if there are no items on the stack;
     * false otherwise.
     */
    override fun isEmpty(): Boolean {
        return items.isEmpty()
    }

/*
     * Pushes given item on the top of the stack
     */
    override fun push(item: T) {
        items.add(item)
    }

/*
     * Removes the item on top of the stack and returns it.
     * If the stack is empty, throws an exception.
     */
    override fun pop(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        return items.removeLast()
    }

/*
     * Returns the item on top of the stack without removing it.
     * If the stack is empty, throws an exception.
     */
    override fun peek(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        return items[items.count() - 1]
    }

/*
     * Returns the number of items on the stack.
     */
    override fun size(): Int {
        return items.count()
    }

/*
     * Convert to string as an array from bottom to top
     */
    override fun toString(): String {
        return items.toString()
    }
}

^^^^
fun toString(number: Int, base: Int): String {
    var n = number
    val stack = ListStack<String>()

val digitStrings = listOf("0", "1", "2", "3", "4", "5",
        "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"
    )

while (n > 0) {
        if (n < base) {
            stack.push(digitStrings[n])
        } else {
            stack.push(digitStrings[n % base])
        }
        n = n / base
    }

var result = ""
    while (!stack.isEmpty()) {
        result = result + stack.pop()
    }
    return result
}

fun main() {
    println(toString(13, 2)) // 1101
}

Each time we go through the first while loop in lines 9–16, we push a character on the stack. When converting 13 to base 2, we see that when the loop exits, the stack would look like Figure 4.6.2. Now we can pop the characters off the stack and concatenate them into the final result, "1101".

🔗

Figure 4.6.2. Strings Placed on the Stack During Conversion
🔗

The previous example gives us some insight into how Kotlin implements a recursive function call. When a function is called in Kotlin, a stack frame is allocated to handle the local variables of the function. When the function returns, the return value is left on top of the stack for the calling function to access. Figure 4.6.3 illustrates the call stack after the return statement on line 22.

🔗

Figure 4.6.3. Call Stack Generated from `toString(13, 2)`
🔗

Notice that the call to toString(2 / 2, 2) defined in Listing 4.4 leaves a return value of "1" on the stack. This return value is then used in place of the function call (toString(1, 2)) in the expression "1" + digitStrings[3 % 2], which will leave the string "11" on the top of the stack. In this way, the Kotlin call stack takes the place of the stack we used explicitly in Listing 4.6.1. In our list-summing example, you can think of the return value on the stack taking the place of an accumulator variable.

🔗

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.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next