Print Numbers by recursion

Question

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?

Challenge

Do it in recursion, not for-loop.

Thoughts

n与n-1的关系其实就是将n-1的所有的结果，加上10 * (n - 1) i (i from 1 - 9) 但是对于2和1不一样，因为1的结果不应该包括0, 所以要单独考虑

Analysis

Solution

class Solution:
    # @param n: An integer.
    # return : A list of integer storing 1 to the largest number with n digits.

    def numbersByRecursion(self, n):
        # write your code here
        if not n:
            return []
        if n == 1:
            return [1,2,3,4,5,6,7,8,9]
        else:
            result = self.printHelper(n)
            result.remove(0)
            return result

    def printHelper(self, n):
        if n == 1:
            return [0,1,2,3,4,5,6,7,8,9]
        result = []
        minorRe = self.printHelper(n-1)
        result += minorRe
        for i in range(1,10):
            newList = []
            for num in minorRe:
                newNum = num + 10 ** (n-1) * i
                newList.append(newNum)
            result += newList

        return result