Given an integer n, return 1 - n in lexicographical order

Question

Eg. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

The below solution works, quite well actually. I found it after struggling a bit, and I can't understand how it's actually working. It seems like pure magic. When we make the recursive call, how in the world is the start argument still 10 after the second time recursing

public static ArrayList<Integer> lexicalOrder(int n) {
    ArrayList<Integer> result = new ArrayList<>();
    dfs(1, 9, n, result);
    return result;
}
private static void dfs(int start, int end, int n, ArrayList<Integer> result){
    for (int i = start; i <= end && i <= n; i++){
        result.add(i);
       //Just printing out the end and start to try to understand
        System.out.println("Start : " + start + " End : " + end);
       //If i is 10, how does 10 * 10 end up as 10 again for several iterations???
        dfs(i * 10, i * 10 + 9, n, result);
    }
}

I don't believe in magic, so can someone please explain how this is working? First iteration start is 1 and end is 9 as expected. Then start is 10 and 19 as I expected on the second iteration. Then, I expect start to be 100, and end to be 109 after we make our next recursive call; however, they are as they were on the previous recursion: 10 and 19.

Answer 1

Basically what it does is go to some number, and append the digits 0 through 9 onto it, then goes to those numbers, and appends 0 through 9 onto it, skipping over the numbers greater than N (13 in this case).

Here's a couple step throughs

It might be easier to see what's happening by looking at "i" centered left.

"i"                                         return
1   //Add to list                           {1}
10  //Add to list                           {1,10}
100 //Bigger than n! (n = 13)               {1,10}
11  //Add to list                           {1,10,11}
110 //Bigger than n! (n = 13)               {1,10,11}
12  //Add to list                           {1,10,11,12}
120 //Bigger than n! (n = 13)               {1,10,11,12}
13  //Add to list                           {1,10,11,12,13}
130 //Bigger than n! (n = 13)               {1,10,11,12,13}
14  //Bigger than n! (n = 13)               {1,10,11,12,13}
2   //Add to list                           {1,10,11,12,13,2}
20  //Bigger than n! (n = 13)               {1,10,11,12,13,2}
3   //Add to list                           {1,10,11,12,13,2,3}
30  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3}
4   //Add to list                           {1,10,11,12,13,2,3,4}
40  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4}
5   //Add to list                           {1,10,11,12,13,2,3,4,5}
50  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4,5}
6   //Add to list                           {1,10,11,12,13,2,3,4,5,6}
60  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4,5,6}
7   //Add to list                           {1,10,11,12,13,2,3,4,5,6,7}
70  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4,5,6,7}
8   //Add to list                           {1,10,11,12,13,2,3,4,5,6,7,8}
80  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4,5,6,7,8}
9   //Add to list                           {1,10,11,12,13,2,3,4,5,6,7,8,9}
90  //Bigger than n! (n = 13)               {1,10,11,12,13,2,3,4,5,6,7,8,9}
10  //Bigger than end! (end = 9)            {1,10,11,12,13,2,3,4,5,6,7,8,9}

A more complete version of what's happening:

lexicalOrder(13)
    result = {}
    dfs(1,9,13,result)  //1 is the smallest digit, 9 is the largest digit,
                        //13 is the largest possible value,
                        //Passed in "result" array to be edited.
        i = start
        //i = 1
        Enter Loop
        result.add(1)
        //result = {1}
        dfs(10,19,13,result)
            i = start
            //i = 10
            Enter Loop
            result.add(10)
            //result = {1,10}
            dfs(100,109,13,result)
                i = start
                //i = 100
                Enter Loop
                Whoops! "i" is greater than "n"! //n = 13
                Exit Loop
            i++
            //i = 11
            result.add(11)
            //result = {1,10,11}
            dfs(110,119,13,result)
                i = start
                //i = 110
                Enter Loop
                Whoops! "i" is greater than "n"! //n = 13
                Exit Loop
            i++
            //i = 12
            result.add(12)
            //result = {1,10,11,12}
            dfs(120,129,13,result)
                i = start
                //i = 120
                Enter Loop
                Whoops! "i" is greater than "n"! //n = 13
                Exit Loop
            i++
            //i = 13
            result.add(13)
            //result = {1,10,11,12,13}
            dfs(130,139,13,result)
                i = start
                //i = 130
                Enter Loop
                Whoops! "i" is greater than "n"! //n = 13
                Exit Loop
            i++
            //i = 14
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 2
        result.add(i)
        //result = {1,10,11,12,13,2}
        dfs(20,29,13,result)
            i = start
            //i = 20
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 3
        result.add(i)
        //result = {1,10,11,12,13,2,3}
        dfs(30,39,13,result)
            i = start
            //i = 30
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 4
        result.add(i)
        //result = {1,10,11,12,13,2,3,4}
        dfs(40,49,13,result)
            i = start
            //i = 40
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 5
        result.add(i)
        //result = {1,10,11,12,13,2,3,4,5}
        dfs(50,59,13,result)
            i = start
            //i = 50
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 6
        result.add(i)
        //result = {1,10,11,12,13,2,3,4,5,6}
        dfs(60,69,13,result)
            i = start
            //i = 60
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 7
        result.add(i)
        //result = {1,10,11,12,13,2,3,4,5,6,7}
        dfs(70,79,13,result)
            i = start
            //i = 70
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 8
        result.add(i)
        //result = {1,10,11,12,13,2,3,4,5,6,7,8}
        dfs(80,89,13,result)
            i = start
            //i = 80
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 9
        result.add(i)
        //result = {1,10,11,12,13,2,3,4,5,6,7,8,9}
        dfs(90,99,13,result)
            i = start
            //i = 90
            Enter Loop
            Whoops! "i" is greater than "n"! //n = 13
            Exit Loop
        i++
        //i = 10
        Whoops! "i" is greater than "end"! //end = 9
    return result // result = {1,10,11,12,13,2,3,4,5,6,7,8,9}

Answer 2

It's very simple. You have both recursion and a loop. Thus the first call to dfs(1,9,13) actually does this:

add 1 to result and call dfs (10,19,13), 
add 2 to result and call dfs (20,29,13)
... 
add 9 to result and call dfs (90,99,13).

Only the call to dfs (10,19,13) actually does anything because in all other cases the first two parameters are greater than the 3rd.

The call to dfs (10,19,13) does this:

add 10 to result and call dfs (100, 109, 13)
add 11 to result and call dfs (110, 119, 13)
add 12 to result and call dfs (120, 129, 13)
add 13 to result and call dfs (130, 139, 13)

it then terminates because 14 is greater than 13.

The behaviour you are seeing, of start and end going back to 10 and 13, are simply a result of this second set of recursive calls terminating and returning to the enclosing loop.