解决递归序列
最近我一直在解决谷歌Foobar的一些挑战，为了好玩，现在我已经被困在其中一个超过4天了。它是关于定义如下递归函数：解决递归序列
R(0) = 1
R(1) = 1
R(2) = 2
R(2n) = R(n) + R(n + 1) + n (for n > 1)
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1)
的挑战是写一个函数answer(str_S)其中str_S是一个整数S，它返回最大n使得R(n) = S的底数为10的字符串表示。如果没有这样的n，则返回“无”。另外，S将是一个不大于10^25的正整数。
我已经调查了很多关于递归函数和关于解决递归关系，但没有运气。我输出了前500个号码，我发现每个号码都没有关系。我使用下面的代码，它使用递归，所以当数字开始变大时它变得非常慢。
def getNumberOfZombits(time):
if time == 0 or time == 1:
return 1
elif time == 2:
return 2
else:
if time % 2 == 0:
newTime = time/2
return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime
else:
newTime = time/2 # integer, so rounds down
return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1
所面临的挑战还包括一些测试用例所以，在这里，他们是：
Test cases
==========
Inputs:
(string) str_S = "7"
Output:
(string) "4"
Inputs:
(string) str_S = "100"
Output:
(string) "None"
我不知道如果我需要解决的递推关系到任何东西简单，但因为有一个甚至一个用于奇数，我觉得很难做到（我还没有在学校中了解到它，所以我对这个主题的所有知识都来自互联网文章）。
所以，在所有指导我完成这个挑战任何帮助将受到欢迎:)
，而不是试图用数学简化这个功能，我简化了Python中的算法。正如@LambdaFairy所建议的那样，我在getNumberOfZombits（time）函数中实现了记忆。此优化加快了功能很多。
然后，我转到下一步，尝试看看这个兔子的输入是什么。我之前通过观察它的情节分析了函数，并且我知道偶数数字先得到更高的输出，并且在奇数达到相同的水平之后才得到更高的输出。由于我们需要输出的最高输入，所以我首先需要在偶数中搜索，然后在奇数中搜索。如你所见，奇数总是比偶数获得更多的时间才能达到相同的输出。
问题是我们无法搜索每次增加1的数字（它太慢了）。我做了什么来解决这个问题就是实现一个类似二进制搜索的算法。首先，我将搜索偶数（使用二进制搜索算法），直到找到一个答案或者我没有更多数字搜索。然后，我对奇数进行了同样的处理（再次使用二进制搜索算法），如果找到了答案，我用它替换了以前的任何答案（因为它必然比前一个答案更大）。
我有我用来解决这个源代码，所以如果有人需要它，我不介意分享吧:)
解决这一难题的关键是使用二进制搜索。从序列发生器可以看到，它们依赖于大致n/2的递归，因此计算R（N）需要大约2 * log2（N）递归调用;当然，你需要为奇数和偶数做到这一点。
这不算太坏，但你需要弄清楚哪里可以找到能够给你输入的N。为了做到这一点，我首先实现了对N的上下界的搜索。我用2的幂乘上N，直到我有N和2N分别为每个序列（奇数和偶数）形成下限和上限。
有了这些界限，我就可以在它们之间进行二分搜索，快速找到N的值，或者它的不存在。
我认为你必须知道一些先进的数学和使用快速矩阵求幂。 – 2014-12-04 19:49:41
这可能有助于：http://*.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python – 2014-12-04 21:14:39
@LambdaFairy也许就是这样吧！我认为这不会有太大的区别，但事实证明，这要比以前快得多！谢谢！我现在试着用它来实现它，我会告诉你它是否做到了这一点：D – 2014-12-04 22:12:27