Print routes on the stairway when only 1 or 2 steps are possible

Question

Given a staircase with N steps, you can go up with 1 or 2 steps each time. Output all possible ways you go from bottom to top.

I'm looking for code review, best practices, optimizations etc. Complexity: O(2ⁿ)

    public final class StairRoutes {

        private StairRoutes() {}

        /**
         * Given a staircase with N steps, you can go up with 1 or 2 steps each time.
         * Output all possible way you go from bottom to top.
         * 
         * @param stepCount     The number of steps in the stairway
         * @return              A list containing all possible routes.
         */
        public static List<List<Integer>> stairClimbingRoutes(int stepCount) {
            if (stepCount <= 0) throw new IllegalArgumentException("The step count: " + stepCount + " should be positive.");


            /* a container containing all the possible routes */
            final List<List<Integer>> stairRoutes = new ArrayList<List<Integer>>();
            calcAllRoutes(stepCount, new LinkedList<Integer>(), stairRoutes);

            return stairRoutes;
        }

        private static void calcAllRoutes(int stepCount, LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            if (stepCount <= 1) {
                populateRoute (stepCount, tempList, stairRoutes);
                return;
            }

            processSteps(stepCount, 1, tempList, stairRoutes);
            processSteps(stepCount, 2, tempList, stairRoutes);
        }

        private static void populateRoute (int numStairs,  LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            if (numStairs == 0) {
                stairRoutes.add(new ArrayList<Integer>(tempList));
                return;
            }
            if (numStairs == 1) {
                tempList.add(1);
                stairRoutes.add(new ArrayList<Integer>(tempList));
                tempList.removeLast();
                return;
            }        
        }


        private static void processSteps(int numStairs, int hopCount, LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            tempList.add(hopCount);
            calcAllRoutes(numStairs - hopCount, tempList, stairRoutes);
            tempList.removeLast();
        }

        public static void main(String[] args) {
            List<List<Integer>> stairRoutes = stairClimbingRoutes(5);
            for (List<Integer> route : stairRoutes) {
                for (Integer stair : route) {
                    System.out.print(stair + ":");
                }
                System.out.println();
            }
        }

}

Answer 1

In general, recursion is a complicated technique. It is often hard to understand the state of the system at any point in time because you have to add a dimension to your thinking.

I consider it to be bad practice to have a recursive process where the recursion is unnecessarily split across multiple methods. In your case, you have a 2-method split in your recursion.

calcAllRoutes calls processSteps
   processSteps calls calcAllRoutes
      calcAllRoutes calls processSteps
         processSteps calls calcAllRoutes
            ...

Sometimes this is not avoidable... but, in this case, it is unnecessary. By splitting the logic in to two methods, it becomes harder to 'grok' the recursion.

Additionally, your previous questions where you have had similar sorts of work, you have always 'defaulted' to using java.util.* collections instead of using simpler mechanisms like arrays of primitives. Arrays are much faster, and smaller, and tend to lead to better structured code. This is because the array is essentially a stack, and popping the stack is as easy as changing it's size.... you do not have to do as much manipulation of the stack head.

Finally, this problem is one which should have a more general solution. You have hard-coded this solution to only work with 1-step and 2-step 'strides'. The problem is actually simpler if you make the stride options a general thing....

Consider this alternative code... it:

1. has a single recursive method.
2. the recursive method has the standard layout:
   • check recursion-ending-conditions
   • initiate further recursion
3. it can use any number of positive-valued strides to get to the destination
4. it is just a single recursive method.
5. it uses an array of primitive ints to accumulate the current combination

So, this code is, in my opinion, preferable:

public class Stairway {

    /**
     * Calculate all possible ways to ascend `steps` stairs, using the different-sized strides provided.
     * @param strides the different number of steps that can be taken.
     * @param steps the number of steps to ascend.
     * @return a list of all step combinations.
     */
    public static final List<int[]> stairClimbingRoutes(int[] strides, int steps) {

        // create the combination stack.
        // Longest possible combination is 1 step each time.
        int[] combination = new int[steps];
        int comblength = 0;

        List<int[]> results = new ArrayList<>();

        recurseRoute(steps, strides, combination, comblength, results);
        return results;
    }

    private static void recurseRoute(final int remaining, final int[] strides,
            final int[] combination, final int comblength, final List<int[]> results) {
        if (remaining < 0) {
            // this combination takes us too far.
            return;
        }
        if (remaining == 0) {
            // this combination is just right.
            results.add(Arrays.copyOf(combination, comblength));
            return;
        }
        // need to go further.
        for (int s : strides) {
            combination[comblength] = s;
            recurseRoute(remaining - s, strides, combination, comblength + 1, results);
        }

    }

    public static void main(String[] args) {

        for (int[] combination : stairClimbingRoutes(new int[] {1, 2}, 10)) {
            int check = 0;
            for (int s : combination) {
                check += s;
            }
            System.out.println("Actual " + check + " using " + Arrays.toString(combination));
        }

    }

}

Answer 2

Very nice code, well done. The first thing that came to mind was that it contains the main() function inside the same class as work is done. This is not bad in itself, but consider to keep it in it's own class. That way the program is better structured.

---

It's not necessary, but consider to also document the private functions. This is especially useful if they do a complex operation or there's some complex interaction with each other.

Don't forget to document the exceptions and limitations on the parameters as well.

---

You're inconsistent with the naming of your variables, in one function it is called stepCount in the next numStairs. Was that an active decision to name it differently?

---

calcAllRoutes(stepCount, new LinkedList<Integer>(), stairRoutes);
...
private static void calcAllRoutes(int stepCount, LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {

Why are you handing it a new list? That list seems only to be used inside calcAllRoutes and as far as I can see does not "leak" outside except for being added to stairRoutes. Shouldn't this be declared inside calcAllRoutes instead?

Also consider if this function should return a List instead of getting one passed.

---

 List<List<Integer>> stairRoutes ...

You could create an object which abstracts some of this away. I would at least wrap the inner List into something like Route which removes most of the functionality of List and instead gives it a nice and clean interface.

Additionally this would allow you to override the toString() method and simplify the code in main():

for (Route route : stairRoutes) {
    System.out.println(route.toString());
}