Print numbers from 1 to the largest number with N digits by recursion.
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].
Do it in recursion, not for-loop.
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> result = new ArrayList<Integer>(); if(n < 1) return result; if(n == 1){ for(int i = 1; i <= 9; i++) result.add(i); return result; } List<Integer> start = numbersByRecursion(n - 1); result.addAll(start); result.add(result.get(result.size() - 1) + 1); int factor = 1; for(int i = 1; i < n; i++) factor *= 10; for(int i = 1; i <= 9; i++){ List<Integer> next = new ArrayList<Integer>(); for(int j = 0; j < start.size(); j++) next.add(i * factor + start.get(j)); result.addAll(next); if(i < 9) result.add(result.get(result.size() - 1) + 1); } return result; } }
lintcode-medium-Print Numbers by Recursion
原文：http://www.cnblogs.com/goblinengineer/p/5352190.html