<p>问题是您的代码将每个递归调用分支为三个新调用。这会导致指数行为。在</p>
<p>不过,好的一点是,大多数调用都是重复的:如果用<code>40</code>调用<code>coinProfit</code>,这将级联到:</p>
<pre><code>coinProfit(40)
- coinProfit(20)
- coinProfit(10)
- coinProfit(6)
- coinProfit(5)
- coinProfit(13)
- coinProfit(10)
</code></pre>
<p>您看到的是大量的工作被重复(在这个小例子中,<code>coinProfit</code>已经在<code>10</code>上调用了两次)。在</p>
<p>您可以使用<em>动态编程</em>来解决这个问题:存储以前的计算结果,防止您在这部分上再次分支<em>。在</p>
<p>可以自己实现动态编程,但可以使用<code>@memoize</code>修饰符自动执行此操作。在</p>
<p>现在这个函数做了很多工作。在</p>
^{pr2}$
<p><code>@memoize</code>对函数进行转换,以便:对于函数,保留已计算输出的数组。如果对于一个给定的输入,输出已经被计算出来,它将被存储在数组中,并立即返回。否则,它将按照您的方法定义进行计算,存储在数组中(供以后使用)并返回。在</p>
<p>正如@steveha指出的,python已经有一个内置的<code>memoize</code>函数,称为<code>lru_cache</code>,更多信息可以在<a href="https://stackoverflow.com/questions/11815873/memoization-library-for-python-2-7">here</a>中找到。在</p>
<hr/>
<blockquote>
<p>A final note is that <code>@memoize</code> or other <em>Dynamic programming</em> constructs, are not the solution to all efficiency problems. First of all <code>@memoize</code> <strong>can</strong> have an impact on side-effects: say your function prints something on <code>stdout</code>, then with <code>@memoize</code> this will have an impact on the number of times something is printed. And secondly, there are problems like the SAT problem where <code>@memoize</code> simply doesn't work at all, because the context itself is exponential (this as far as we know). Such problems are called <em>NP-hard</em>.</p>
</blockquote>