擅长:python、mysql、java
<p>我是这样理解你的问题的:你有一个公式<code>x_n = x_{n-1} * (x_{n-1} + 1)/2</code>,递归基被定义为<code>x_1 = 20</code>(或<code>x_2 = 20</code>)?你的描述不清楚)。求解递归的最有效方法是自下而上方法,当您从<code>x_1</code>开始,然后计算<code>x_2</code>等。另一种方法是使用动态规划/记忆:</p>
<pre><code>mem={}
def f(x):
if x == 1: # base case
return 20
if not x in mem: # if we did not calculate it before - calculate
mem[x] = f(x-1) * (f(x-1) +1) / 2
return mem[x] # otherwise return it
print f(1)
print f(2)
print f(3)
</code></pre>
<p>印刷品</p>
<pre><code>20
210
22155
</code></pre>
<p><code>f(20)</code>打印有点大,所以我将打印其中的位数:</p>
<pre><code>print "number of digits: %s" % len(str(f(20)))
number of digits: 530115
</code></pre>
<p>代码在我的桌面上运行大约需要9秒钟:</p>
<pre><code>import timeit
mem={}
print "Execution time: %s" % timeit.Timer("len(str(f(20)))",
setup = "from __main__ import f").timeit(1)
</code></pre>