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

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(2n)

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> stairClimbingRoutes(int stepCount) {
            if (stepCount > stairRoutes = new ArrayList>();
            calcAllRoutes(stepCount, new LinkedList(), stairRoutes);

            return stairRoutes;
        }

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

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

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

}

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:

• has a single recursive method.

• the recursive method has the standard layout:

• check recursion-ending-conditions

• initiate further recursion

• it can use any number of positive-valued strides to get to the destination

• it is just a single recursive method.

• 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 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 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 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));
        }

    }

}

StackExchange Code Review Q#41448, answer score: 6