题目

假设可以不考虑计算机运行资源（如内存、堆栈）的限制，以下Python3代码预期的输出结果是

def rec(n):
    if n < 2:
        return 1
    return rec(n // 2) + rec(n // 4)
print(rec(12345678987654321))

print(rec(123456789))可以很容易跑出结果317811，但是print(rec(12345678987654321))运行了一晚上也没出来结果。
PS. 题目来自朋友圈一个同学去360的面试题。

联想

递归是有规律的。联想到高中的数学归纳法，可以从小的数据慢慢往后推倒。从小数字推到大数字。
有点逆向思维的意思。题目中的递归是从大数字慢慢推到小数字，直至递归出口。

找规律

(0) = 1
(1) = 1
(2) = (1) + (0) = 1 + 1 = 2
(3) = (1) + (0) = 1 + 1 = 2
(4) = (2) + (1) = 3
(5) = (2) + (1) = 3
(6) = (3) + (1) = 3
(7) = (3) + (1) = 3
(8) = (4) + (2) = 5
…
写多了就会发现规律：把该数转化为二进制数。二进制数的长度相同，则结果相同。其实，除以2和除以4也能看出，大概跟二进制有关系。

思考

把一个十进制的数n表示成二进制数为abcde…xyz，它的rec应该是去掉末一位abcde…xy的rec加上去掉末两位abcde…x的rec，即
rec(abcde…xyz) = rec(abcde…xy) + rec(abcde…x)
似曾相识的感觉！有点像斐波那契数列！是变形的斐波那契数列！是关于二进制数长度的斐波那契数列，即斐波那契数列的下标是二进制数的长度。

转化为迭代

#! /usr/bin/env python
from math import log
# n = 123456789
n = 12345678987654321
length = int(log(n, 2)) + 1
a, b = 0, 1
for i in range(length):
    a, b = b, a + b
print b

output: 139583862445

1
2
3

In [1]: bin(8)
Out[1]: '0b1000'
# 结果是字符串，但有0b标识为二进制

总结

可以使用较小的数，两个代码同时运行，验证结果。
再大的数n，也可以迅速算出结果。因为知道n对应的二进制数有多少位即可。

启示

1、有时问题比较抽象，可以举几个简单的例子，实际笔算一下，感受一下过程，说不准灵感就来了。
2、有时候思考了很久还没有结果，那就直接去找答案吧，避免长时间的挫败感。说不准会有醍醐灌顶的效果。
3、有的题目可能会有多种解法。多种解法综合比较一下，或许有意想不到的收获。
4、思考的过程是值得的，沿途的风景会很美！慢慢培养成就感~