Print Numbers by Recursion

Question

  1. Print numbers from 1 to the largest number with N digits by recursion.
  3. Example
  4. Given N = 1, return [1,2,3,4,5,6,7,8,9].
  6. Given N = 2, return [1,2,3,4,5,6,7,8,9,10,11,12,...,99].
  8. Note
  9. It's pretty easy to do recursion like:
  11. recursion(i) {
  12.     if i > largest number:
  13.         return
  14.     results.add(i)
  15.     recursion(i + 1)
  16. }
  17. however this cost a lot of recursion memory as the recursion depth maybe very large.
  18. Can you do it in another way to recursive with at most N depth?
  20. Challenge
  21. Do it in recursion, not for-loop.

题解

从小至大打印 N 位的数列，正如题目中所提供的 recursion(i), 解法简单粗暴，但问题在于 N 稍微大一点时栈就溢出了，因为递归深度太深了。能联想到的方法大概有两种，一种是用排列组合的思想去解释，把0~9当成十个不同的数(字符串表示)，塞到 N 个坑位中，这个用 DFS 来解应该是可行的；另一个则是使用数学方法，依次递归递推，比如 N=2 可由 N=1递归而来，具体方法则是乘10进位加法。题中明确要求递归深度最大不超过 N, 故 DFS 方法比较危险。

Java

  1. public class Solution {
  2.     /**
  3.      * @param n: An integer.
  4.      * return : An array storing 1 to the largest number with n digits.
  5.      */
  6.     public List<Integer> numbersByRecursion(int n) {
  7.         List<Integer> result = new ArrayList<Integer>();
  8.         if (n <= 0) {
  9.             return result;
  10.         }
  11.         helper(n, result);
  12.         return result;
  13.     }
  15.     private void helper(int n, List<Integer> ret) {
  16.         if (n == 0) return;
  17.         helper(n - 1, ret);
  18.         // current base such as 10, 20, 30...
  19.         int base = (int)Math.pow(10, n - 1);
  20.         // get List size before for loop
  21.         int size = ret.size();
  22.         for (int i = 1; i < 10; i++) {
  23.             // add 10, 100, 1000...
  24.             ret.add(i * base);
  25.             for (int j = 0; j < size; j++) {
  26.                 // add 11, 12, 13...
  27.                 ret.add(ret.get(j) + base * i);
  28.             }
  29.         }
  30.     }
  31. }

源码分析

递归步的截止条件n == 0, 由于需要根据之前 N-1 位的数字递推，base 每次递归一层都需要乘10，size需要在for循环之前就确定。

复杂度分析

添加 10^n 个元素，时间复杂度 O(10^n), 空间复杂度 O(1).

Reference