# Print Numbers by Recursion ### Source - lintcode: [(371) Print Numbers by Recursion](http://www.lintcode.com/en/problem/print-numbers-by-recursion/) ~~~ 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. ~~~ ### 題解 從小至大打印 N 位的數列，正如題目中所提供的 `recursion(i)`, 解法簡單粗暴，但問題在于 N 稍微大一點時棧就溢出了，因為遞歸深度太深了。能聯想到的方法大概有兩種，一種是用排列組合的思想去解釋，把0~9當成十個不同的數(字符串表示)，塞到 N 個坑位中，這個用 [DFS](# "Depth-First Search, 深度優先搜索") 來解應該是可行的；另一個則是使用數學方法，依次遞歸遞推，比如 N=2 可由 N=1遞歸而來，具體方法則是乘10進位加法。題中明確要求遞歸深度最大不超過 N, 故 [DFS](# "Depth-First Search, 深度優先搜索") 方法比較危險。 ### Java ~~~ 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) { 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 == 0`, 由于需要根據之前 N-1 位的數字遞推，`base` 每次遞歸一層都需要乘10，`size`需要在`for`循環之前就確定。 ### 復雜度分析 添加 10n10^n10n 個元素，時間復雜度 O(10n)O(10^n)O(10n), 空間復雜度 O(1)O(1)O(1). ### Reference - [Lintcode: Print Numbers by Recursion | codesolutiony](https://codesolutiony.wordpress.com/2015/05/21/lintcode-print-numbers-by-recursion/)