Title: Recursion & Stacks
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Recursion and Stacks

Factorial.java


import java.util.Scanner;

public class Factorial {

    long factorial_recursive(int n)
    {
        if (n== 1)
            return 1;
        return n* factorial_recursive(n-1);
    }
    long factorial_loop(int n)
    {
        long answer=1;
        for (int i=2; i <= n; i++)
            answer *= i;

        return answer;
    }
    public static void main(String[] args) {
        System.out.println("Enter n: ");
        Scanner keyboard = new Scanner(System.in);

        Factorial fact = new Factorial();

        int n = keyboard.nextInt();

        System.out.println("factorial_recursive =" + fact.factorial_recursive(n));
        System.out.println("factorial_loop =" + fact.factorial_loop(n));

    }

}



When Recursion is a bad choice: Fibonacci

We will be doing some timing and you will need:

Timer.java

Try the following with an N in the vacinity of 43, 44, 45, 46

I get run times of 2.3, 3.7, 6, 9.7 seconds

The execution time seems to go up by a factor of about 1.6 for each increase of N


import java.util.Scanner;

public class Fibonacci {

    long fibonacci_recursive(int n)
    {
        if (n < 2)
            return n;
        else
            return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
    }

    long fibonacci_loop(int n)
    {
        long oldest = 0;
        long previous = 1;
        long fib = n;
        for (int i=2; i <= n; i++)
        {
            fib = oldest+previous;
            oldest = previous;
            previous = fib;
        }

        return fib;
    }
    public static void main(String[] args) {
        System.out.println("Enter n: ");
        Scanner keyboard = new Scanner(System.in);

        Fibonacci fib = new Fibonacci();

        int n = keyboard.nextInt();


        System.out.println("fibonacci_loop =" + fib.fibonacci_loop(n));

        Timer timer = new Timer();
        timer.start();
        System.out.println("fibonacci_recursive =" + fib.fibonacci_recursive(n));
        timer.stop();
        System.out.println("time = "+timer.time());

    }

}



Remembering the intermediate results and fixing the slowness;


import java.util.Scanner;

public class Fibonacci {

    long[] saved_values;

    long fibonacci(int n)
    {
        saved_values = new long[n+1];
        for (int i=0; i<= n; i++)
            saved_values[i] = -1;

        return fibonacci_recursive(n);
    }
    long fibonacci_recursive(int n)
    {
        if (saved_values[n] >= 0)
            return saved_values[n];

        long answer = n;
        if (n >= 2)
        {
            answer = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
        }
        saved_values[n] = answer;
        return answer;
    }


    public static void main(String[] args) {
        System.out.println("Enter n: ");
        Scanner keyboard = new Scanner(System.in);

        Fibonacci fib = new Fibonacci();

        int n = keyboard.nextInt();


        Timer timer = new Timer();
        timer.start();
        System.out.println("fibonacci_recursive =" + fib.fibonacci(n));
        timer.stop();
        System.out.println("time = "+timer.time());

    }

}



Knapsack




import java.util.Scanner;

public class Knapsack {
    boolean[] best_solution;
    int best_solution_weight;

    boolean[] trial_solution;
    int[] item_weights;
    int knapsack_weight;
    int num_objects;

    void solve()
    {
        best_solution = new boolean[num_objects];
        trial_solution = new boolean[num_objects];
        best_solution_weight = -1;
        solve(0, 0);
    }

    void solve(int step, int curr_solution_weight)
    {

          if (step == num_objects)
            {
              // At this point we have finished looking at all objects
              // and we take a look at our temporary solution
              // and see if it's current weight is a better solution
              // than the best so far.
              if (curr_solution_weight > best_solution_weight)
                {
                  best_solution_weight = curr_solution_weight;
                  for (int i=0; i < num_objects; i++)
                      best_solution[i] = trial_solution[i];
                }
              return;
            }


          // First possiblity is to have this object in if it fits
          int new_weight = curr_solution_weight + item_weights[step];
          if (new_weight <= knapsack_weight)
            {
              trial_solution[step] = true;
              solve(step +1 , new_weight);
            }

          // Second possiblitily is to not have this object in
          trial_solution[step] = false;
          solve (step +1, curr_solution_weight);
    }

    void setupKnapsack(int n, int smallest, int largest, int knapsack_percentage)
    {
        num_objects = n;
        item_weights = new int[n];
        int total =0;
        for (int i=0; i < n; i++)
        {
            item_weights[i] = smallest + (int)((largest - smallest)*Math.random());
            total += item_weights[i];
            System.out.println("item("+i+") ="+ item_weights[i]);
        }

        knapsack_weight = (total * knapsack_percentage)/ 100;
        System.out.println("knapsack_weight_limit="+ knapsack_weight);

    }


    void printSolution()
    {
      System.out.println("Solution size =" + best_solution_weight);
      System.out.println("Items in solution: ");
      int check_weight=0;
      for (int i=0; i < num_objects; i++)
        {
          if (best_solution[i])
            {
              System.out.print(" " + i);
              check_weight += item_weights[i];
            }
        }
      System.out.println();
      System.out.println(" total checked weight =" + check_weight );
    }

    public static void main(String[] args) {
        System.out.println("enter in N:");
        Scanner keyboard = new Scanner(System.in);
        int n= keyboard.nextInt();


        Knapsack knapsack = new Knapsack();

        knapsack.setupKnapsack(n, 10, 100, 75);

        Timer timer= new Timer();
        timer.start();
        knapsack.solve();
        timer.stop();
        System.out.println("time="+ timer.time());

        knapsack.printSolution();

    }

}



Timings:

You will note that for each increase of N by 1, your execution time will roughly double. So we would say that the speed of this algorithm is:

O(2^N)

On my computer, I get the following timings:

N | Execution Time (seconds)
29 | 3.6
30 | 7.4
31 | 14
32 | 27.7

Knapsack with a Stack




import java.util.Scanner;
import java.util.Stack;

class Choice
{
    boolean state;
    int curr_solution_weight;
    Choice(boolean s, int w)
    {
        state = s;
        curr_solution_weight = w;
    }
}

public class Knapsack_Stack {

    boolean[] best_solution;
    int best_solution_weight;

    boolean[] trial_solution;
    int[] item_weights;
    int knapsack_weight;
    int num_objects;

    void solve()
    {
        best_solution = new boolean[num_objects];
        trial_solution = new boolean[num_objects];
        best_solution_weight = -1;
        solve_with_stack();
    }
    void solve_with_stack()
    {
        Stack<Choice> myStack = new Stack<Choice>();
        boolean continueFlag = true;

        while (continueFlag)
        {
            int depth=myStack.size();
            if (depth == num_objects)
            {
                int curr_solution_weight = myStack.peek().curr_solution_weight;
                if (curr_solution_weight > best_solution_weight)
                {
                    best_solution_weight = curr_solution_weight;
                    for (int i=0; i < num_objects; i++)
                        best_solution[i] = trial_solution[i];
                }
                myStack.pop(); // Since we try the True branch first, we can skip the T-->F on the leaf node
                if (backtrack(myStack))
                {
                    continueFlag = false;
                    break;
                }
            }
            else
            {
                int curr_wt = 0;
                int tmp_wt=0;
                if (depth  > 0)
                    curr_wt = myStack.peek().curr_solution_weight;

                tmp_wt = curr_wt + item_weights[depth];
                if (tmp_wt <= knapsack_weight)
                {
                    myStack.push(new Choice(true, tmp_wt));
                    trial_solution[depth] = true;
                }
                else
                {
                    myStack.push(new Choice(false, curr_wt));
                    trial_solution[depth] = false;
                }

            }
        }
    }

    boolean backtrack(Stack<Choice>  s)
    {
        while (s.size() > 0 && s.peek().state == false)
        {
            s.pop();
        }

        int depth = s.size();
        if (depth == 0) return true;
        // Changing a true to a false
        s.peek().state = false;
        trial_solution[depth-1] = false;
        s.peek().curr_solution_weight -= item_weights[depth-1];
        return false;
    }

    void setupKnapsack(int n, int smallest, int largest, int knapsack_percentage)
    {
        num_objects = n;
        item_weights = new int[n];
        int total =0;
        for (int i=0; i < n; i++)
        {
            item_weights[i] = smallest + (int)((largest - smallest)*Math.random());
            total += item_weights[i];
            System.out.println("item("+i+") ="+ item_weights[i]);
        }

        knapsack_weight = (total * knapsack_percentage)/ 100;
        System.out.println("knapsack_weight_limit="+ knapsack_weight);

    }


    void printSolution()
    {
        System.out.println("Solution size =" + best_solution_weight);
        System.out.println("Items in solution: ");
        int check_weight=0;
        for (int i=0; i < num_objects; i++)
        {
            if (best_solution[i])
            {
                System.out.print(" " + i);
                check_weight += item_weights[i];
            }
        }
        System.out.println();
        System.out.println(" total checked weight =" + check_weight );
    }

    public static void main(String[] args) {
        System.out.println("enter in N:");
        Scanner keyboard = new Scanner(System.in);
        int n= keyboard.nextInt();


        Knapsack_Stack knapsack = new Knapsack_Stack();

        knapsack.setupKnapsack(n, 10, 100, 75);

        Timer timer= new Timer();
        timer.start();
        knapsack.solve();
        timer.stop();
        System.out.println("time="+ timer.time());

        knapsack.printSolution();

    }

}



Summary

My Stack solution for Knapsack is not as easy to understand and it is slower

I believe I could spend some time and make it faster. Notice the "new Choice()" calls everytime we push onto the stack. This is overhead we didn't have in the Recursive style because the compiler can create stack frames very efficiently.

General comments about Stack approaches and Recursion

- There are some problems which fit the model of Recursion or Stacks. These 2 models seem to give us ways to solve problems that would be difficult to solve otherwise.
- Often if we can write a program as a Recursive algorithm, we could probably also write it as a stack program.
- We have seen stupid situations to use Recursion (simple Fibonacci).
- We will see some powerful uses of Recursion in the Towers of Hanoi.
- Languages, and Compilers are often written with either a Recursive or Stack algorithm because it is a good fit.
- You might not be too impressed with the Stack approach so far.
- I have a few more examples to show you : N-Queens (I will do both Recursion and Stack approaches).
- Solving Maizes - in this case I find the Stack works the best
- A program that I don't currently have (I may have it in the future) is solving Sudoku problems. A Stack is a very nice way to solve Sudoku.
- One last program that could be solved with either Recursion or Stacks is the Traveling Salesman problem.

Last Updated: July 22, 2014 10:03 PM