你永远想不到他们会写出怎样奇怪的程序算斐波拉契数。

18/12/28 更新

众所周知,"Hello, world"是初学某种编程语言者最常写的程序,通过这个程序可以体现某种语言最基本的输出方式。其实斐波拉契数列也是我们常用于举例的程序之一,它体现的是语言中判断循环语句的设计。

斐波拉契数列是这样一个数列:数列的前2项为1, 1,之后每一项为它之前的两项之和,[1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...]这样的一个数列。

以下我就用Python描述几种奇怪的写法。

递推法

递推是求斐波拉契数列最基本的写法了。

def f(n: int):
    if n<3:
        if n in [1, 2]:
            return 1
    else:
        x, y = 1, 1
        for _ in range(n-2):
            x, y = y, x+y
        return y

print(f(10))

output: 55

递归法

递归也是求斐波拉契数列的一种常用的方法(事实上他们似乎一直用这个算法来演示递归)。

def f(n: int):
    if n <= 2:
        return 1
    else:
        return f(n-1)+f(n-2)

print(f(10))

output: 55

但是这样递归的速度是很慢的,因为在递归的过程中会有很多相同的运算需要重复运算。
这时就可以用functools中的lru_cache

from functools import lru_cache

@lru_cache()
def g(n: int):
    if n <= 2:
        return 1
    else:
        return g(n-1)+g(n-2)

效果如下:

>>> test(f, 35, info='未使用缓存')
未使用缓存: 9227465 耗时: 1.567599
>>> test(g, 35, info='使用缓存')
使用缓存: 9227465 耗时: 0.000008
>>> test(g, 200, info='使用缓存')
使用缓存: 280571172992510140037611932413038677189525 耗时: 0.000566
>>> test(g, 500, info='使用缓存')
使用缓存: 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125 耗时: 0.001339

一个奇怪的求法

当年学Python时学到了yield表达式,就写出了以下代码:

#from itertools import islice as sl
def a():
  pre, bef = 0, 0
  while True:
    pre, bef = bef, (yield bef+pre)

def f():
  x = 1
  at = a()
  at.send(None)
  while True:
    yield x
    x = at.send(x)

#print(*list(sl(f(), 0, 20)))
x = f()
print(*[next(x) for _ in range(10)])

output: 1 1 2 3 5 8 13 21 34 55

显然,这本质上就是第一种算法递推表达式的极其复杂的另一种版本。以下写一个简单点的:

def f():
  a, b = 1, 1
  yield a
  yield b
  while True:
    a, b = b, a+b
    yield b

使用lambda表达式(1)

以上方法中我们都将算法细节写进了一个叫做f的函数中,而显然这个函数逻辑非常简单。lambda表达式也是一个函数,它是匿名函数,即它可以不用绑定到一个函数名上。lambda表达式形如 lambda A: B ,其中A是输入的参数,B是返回值。那么我们可以将之前的递归算法写成如下:

lambda n: 1 if n<=2 else f(n-1)+f(n-2)

显然,这个函数是不能运行的。我们之前说过lambda表达式是匿名函数,所以没法进行递归调用自身。所以我们只能将它绑定到一个函数名上:

f = lambda n: 1 if n<=2 else f(n-1)+f(n-2)
print(f(10))

output: 55

但是这样就不太漂亮了,而且容易出问题。

使用lambda表达式(2)

lambda表达式是匿名函数,所以没法进行递归调用自身

上文我是这么说的,然而这种说法是错的。

玩函数式编程的小明告诉我,使用一种叫做 不动点组合子 的高阶函数就可以在不使用名字的情况下将匿名函数绑定到自身。

Z组合子:

Z = lambda f: (lambda x: (lambda y: f(x(x))(y)))(lambda x: (lambda y: f(x(x))(y)))

小明的演示程序如下:

1

@Z
def fibs(this):
  def inner_fibs(n):
    if n <= 2: return 1
    else: return this(n-1) + this(n-2)
  return inner_fibs
print(fibs(10))

2

fibs = lambda f: lambda n: 1 if n<= 2 else f(n-1)+f(n-2)
print(Z(fibs)(10))

Y组合子:

Y = lambda f: (lambda x: lambda n: f(x(x))(n))(lambda x: lambda n: f(x(x))(n))

通过Y组合子将我们刚才的匿名函数绑定:

fib = lambda f: lambda n: 1 if n<=2 else f(n-1)+f(n-2)
print(Y(fib)(10))

output: 55

虽然看起来比较绕,但还算比较好理解。

最后,我们还能直接把所有代码写进一行中,这样就比较好看了

print((lambda f: (lambda x: (lambda y: f(x(x))(y)))(lambda x: (lambda y: f(x(x))(y))))(lambda f: lambda n: 1 if n<= 2 else  f(n-1) + f(n-2))(10))

output: 55