https://www.lintcode.com/en/problem/print-numbers-by-recursion/
Example
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?
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].
https://zhengyang2015.gitbooks.io/lintcode/print_numbers_by_recursion_371.html
递归求解n时，可以对n－1位置上的数从0-9遍历，依次类推直到最后一位。
public List<Integer> numbersByRecursion(int n) {
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);
}
}res = {1, 2, 3, 4, 5, 6, 7, 8, 9};
base = helper(n-1, res); //10
//i = 1 ~ 9;
for i:
curbase = i * base; //10, 20, 30, 40, ... , 80, 90
res.add(curbase); // 10; 20; ... ; 80; 90
//j = index of res;
for j:
res.add(curbase + res.get(j)); //11, 12, 13, ... , 18, 19;
//21, 22, 23, ... , 28, 29;
//...
归纳一下，首先，计算最高位存入base，然后，用1到9倍的base（curbase）和之前res里已经存入的所有的数（res.size()个）循环相加，再存入res，更新res.size，计算更高位直到base等于10^n...
public List<Integer> numbersByRecursion(int n) {
List<Integer> res = new ArrayList<Integer>();
if (n >= 0) {
helper(n, res);
}
return res;
}
public int helper(int n, List<Integer> res) {
if (n == 0) return 1;
int base = helper(n-1, res);
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;
}
递归步的截止条件
n == 0, 由于需要根据之前 N-1 位的数字递推，base 每次递归一层都需要乘10，size需要在for循环之前就确定。 public List<Integer> numbersByRecursion(int n) {
List<Integer> result = new ArrayList<Integer>();
if (n <= 0) {
return result;
}
helper(n, result);
return result;
}
private void helper(int n, List<Integer> ret) {
if (n == 0) return;
helper(n - 1, ret);
// current base such as 10, 20, 30...
int base = (int)Math.pow(10, n - 1);
// get List size before for loop
int size = ret.size();
for (int i = 1; i < 10; i++) {
// add 10, 100, 1000...
ret.add(i * base);
for (int j = 0; j < size; j++) {
// add 11, 12, 13...
ret.add(ret.get(j) + base * i);
}
}
}
n与n-1的关系其实就是将n-1的所有的结果，加上10 * (n - 1) i (i from 1 - 9) 但是对于2和1不一样，因为1的结果不应该包括0, 所以要单独考虑
recursion(i), 解法简单粗暴，但问题在于 N 稍微大一点时栈就溢出了，因为递归深度太深了。能联想到的方法大概有两种，一种是用排列组合的思想去解释，把0~9当成十个不同的数(字符串表示)，塞到 N 个坑位中，这个用 DFS 来解应该是可行的；另一个则是使用数学方法，依次递归递推，比如 N=2 可由 N=1递归而来，具体方法则是乘10进位加法。题中明确要求递归深度最大不超过 N, 故 DFS 方法比较危险。