我不确定我是不是在重复某人的意思但前段时间有人写了一个y算子用于递归调用函数

def tail_recursive(func):
  y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
  def wrap_func_tail(*args):
    out = y_operator(*args)
    while callable(out): out = out()
    return out
  return wrap_func_tail

然后递归函数需要形式:

def my_recursive_func(g):
  def wrapped(some_arg, acc):
    if <condition>: return acc
    return g(some_arg, acc)
  return wrapped

# and finally you call it in code

(tail_recursive(my_recursive_func))(some_arg, acc)

对于斐波那契数，你的函数是这样的:

def fib(g):
  def wrapped(n_1, n_2, n):
    if n == 0: return n_1
    return g(n_2, n_1 + n_2, n-1)
  return wrapped

print((tail_recursive(fib))(0, 1, 1000000))

输出:

..684684301719893411568996526838242546875

(实际上是数字的音调)

我知道这是一个老问题，但对于那些阅读的人来说，我建议不要使用递归来解决这样的问题——列表要快得多，并且完全避免递归。我将这样实现:

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(在xrange中使用n+1，如果你从0开始计数你的斐波那契数列，而不是从1开始。)

当然，斐波那契数可以用O(n)计算，应用比奈公式:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

正如评论者指出的那样，它不是O(1)，而是O(n)，因为2**n。另一个不同之处在于，您只能得到一个值，而使用递归则可以得到该值之前的所有Fibonacci(n)值。

使用一种保证尾部调用优化的语言。或者使用迭代。或者，和装饰师一起玩。

我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

这仍然是递归的，但是使用了一个简单的哈希表，允许重用以前计算的斐波那契数，而不是重新计算。

如果你经常需要改变递归限制(例如在解决编程难题时)，你可以定义一个简单的上下文管理器，像这样:

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

然后调用具有自定义限制的函数，您可以这样做:

with recursionlimit(1500):
    print(fib(1000, 0))

从with语句体退出时，递归限制将恢复到默认值。

附注:您可能还想增加Python进程的堆栈大小，以获得较大的递归限制值。例如，这可以通过ulimit shell内置或limits.conf(5)文件来完成。