Print Numbers by Recursion

Print numbers from 1 to the largest number with N digits by recursion.

Have you met this question in a real interview? 

Yes

Example

Given N = 1, return [1,2,3,4,5,6,7,8,9].

Given N = 2, return [1,2,3,4,5,6,7,8,9,10,11,12,...,99].

Note

It's pretty easy to do recursion like:

recursion(i) {
    if i > largest number:
        return
    results.add(i)
    recursion(i + 1)
}

however this cost a lot of recursion memory as the recursion depth maybe very large. Can you do it in another way to recursive with at most N depth?

Challenge

Do it in recursion, not for-loop.

TLE:
public class Solution {
    /**
     * @param n: An integer.
     * return : An array storing 1 to the largest number with n digits.
     */
    public List<Integer> numbersByRecursion(int n) {
        // write your code here
        List<Integer> res = new ArrayList<Integer>();
        while(n > 0){
            printing(res, n);
            n--;
        }
        return res;
       
    }
   
    private void printing(List<Integer> res, int base){
        int start = (int) (Math.pow(10, base) - 1);
        int end = (int) (Math.pow(10, base - 1));
        for(int i = start ; i >= end; i--){
            res.add(0, i);
        }
    }
}

public class Solution {
    /**
     * @param n: An integer.
     * return : An array storing 1 to the largest number with n digits.
     */
    public List<Integer> numbersByRecursion(int n) {
        // write your code here
        List<Integer> res = new ArrayList<Integer>();
        if(n > 0){
            printing(res, n);
        }
        return res;
       
    }
   
    private int printing(List<Integer> res, int n){
        if(n == 0){
            return 1;
        }
        int base = printing(res, n-1);
        int size = res.size();
        for(int i = 1 ; i <= 9; i++){
            int curBase = i * base;
            res.add(curBase);
            for(int j = 0; j < size; j++){
                res.add(curBase + res.get(j));
            }
        }
       
        return base * 10;
    }
}