Lintcode371 Print Numbers by Recursion solution 题解

look_w

【题目描述】

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?

用递归的方法找到从1到最大的N位整数。

【注】用下面这种方式去递归其实很容易：

recursion(i) {

if i > largest number:

return

results.add(i)

recursion(i + 1)

}

但是这种方式会耗费很多的递归空间，导致堆栈溢出。你能够用其他的方式来递归使得递归的深度最多只有 N 层么？

【题目链接】

www.lintcode.com/en/problem/print-numbers-by-recursion/

【题目解析】

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