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.

import java.util.ArrayList;
import java.util.NoSuchElementException;
class Stack<T> {
    ArrayList<T> items;

public Stack() {
        this.items = new ArrayList<T>();
    }

public boolean isEmpty() {
        return (this.items.isEmpty());
    }

public void push(T item) {
        this.items.add(item);
    }

public T pop() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Stack is empty.");
        }
        return this.items.remove(items.size() - 1);
    }

public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Stack is empty.");
        }
        return this.items.get(items.size() - 1);
    }

public int size() {
        return this.items.size();
    }

public String toString() {

if (!this.items.isEmpty()) {
            String arrString = this.items.toString();
            // remove open and closing bracket
            return "bottom ->" + arrString + "<- top";
        } else {
            return "<<empty stack>>";
        }
    }
}

^^^^
public class ConvertViaStack {

public static String convert(int n, int base) {
        Stack<String> rStack = new Stack<>();

String [] digitStrings = {"0", "1", "2", "3", "4", "5",
            "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};

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

String result = "";
        while (! rStack.isEmpty()) {
            result = result + rStack.pop();
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(convert(13, 2)); // 1101
    }
}

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

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 Java implements a recursive method call. When a method is called in Java, a stack frame is allocated to handle the local variables of the method. When the method returns, the return value is left on top of the stack for the calling method to access. Figure 4.6.3 illustrates the call stack after the return statement on line 9.

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

Notice that the call to convert(2 / 2, 2) defined in Listing 4.4 leaves a return value of "1" on the stack because we have reached a base case. This return value is then used in place of the method call (convert(1, 2)) in the expression "1" + convert[3 % 2], which will leave the string "11" on the top of the stack. In this way, the Java call stack takes the place of the stack we used explicitly in Listing 4.6.1. In our array-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 method. Even though we are calling the same methodd over and over, each call creates a new scope for the variables that are local to the method.

You have attempted of activities on this page.

Prev Top Next