lintcode:Print Numbers by Recursion

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

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?

class Solution {
private:

    void numbersByRecursionHelper(int n, vector<int> &retVector)
    {
        if (n == 0)
            return;
            
        numbersByRecursionHelper(n-1, retVector);
        int curSize = retVector.size();
        
        for (int i=pow(10, n-1); i<=9*pow(10, n-1); i+=pow(10,n-1))
        {
            for (int idx=0; idx<curSize; idx++)
            {
                retVector.push_back(i+retVector[idx]);
            }
        }
    }
    
public:
    /**
     * @param n: An integer.
     * return : An array storing 1 to the largest number with n digits.
     */
     
    vector<int> numbersByRecursion(int n) {
        // write your code here
        vector<int> retVector;
        retVector.push_back(0);
        
        numbersByRecursionHelper(n, retVector);

        vector<int> res(retVector.begin()+1, retVector.end());
        
        return res;
    }
};