【題目描述】
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位整數(shù)痹屹。
【注】用下面這種方式去遞歸其實很容易：
recursion(i) {
if i > largest number:
return
results.add(i)
recursion(i + 1)
}
但是這種方式會耗費很多的遞歸空間阁猜，導致堆棧溢出。你能夠用其他的方式來遞歸使得遞歸的深度最多只有 N 層么些膨？
【題目鏈接】
www.lintcode.com/en/problem/print-numbers-by-recursion/
【題目解析】
從小至大打印 N 位的數(shù)列谢肾，正如題目中所提供的recursion(i), 解法簡單粗暴腕侄，但問題在于 N 稍微大一點時棧就溢出了，因為遞歸深度太深了芦疏。能聯(lián)想到的方法大概有兩種冕杠，一種是用排列組合的思想去解釋，把0~9當成十個不同的數(shù)(字符串表示)酸茴，塞到 N 個坑位中分预，這個用DFS來解應該是可行的；另一個則是使用數(shù)學方法薪捍，依次遞歸遞推笼痹，比如 N=2 可由 N=1遞歸而來配喳，具體方法則是乘10進位加法。題中明確要求遞歸深度最大不超過 N, 故DFS方法比較危險凳干。
【參考答案】
