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);
}
}
}