Print Numbers by Recursion 371

Question

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

Notice

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?

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].

Challenge

Do it in recursion, not for-loop.

Solution

在求n-1位数到n位数的时候，先求n-2位数到n-1位数，就如同下面一样：

递归求解n时，可以对n－1位置上的数从0-9遍历，依次类推直到最后一位。

代码如下：

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 < 1){
            return res;
        }

        helper(n, 0, res);
        return res;
    }

    //ans在这里可以看成前一位的值，在递归过程中会乘以n－1次10，即10^(n-1)
    private void helper(int n, int ans, List<Integer> res){
        if(n==0){
            if(ans>0){
                res.add(ans);
            }
            return;
        }

        int i;
        for(i=0; i<=9; i++){
            helper(n-1, ans*10+i, res);
        }
    }
}