当前位置： 文江博客话题详情

最大递归深度是多少？如何增加它？

发布于 2024-09-11 21:59:44 字数 316 浏览 3 评论 0原文

我这里有一个尾递归函数：

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

它最多可以工作到n=997，然后它就会中断并抛出一个RecursionError：比较中超出了最大递归深度。这只是堆栈溢出吗？有办法绕过它吗？

原文

I have this tail recursive function here:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

It works up to n=997, then it just breaks and spits out a RecursionError: maximum recursion depth exceeded in comparison. Is this just a stack overflow? Is there a way to get around it?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（19）

妖妓 2024-09-18 21:59:44

是的，它可以防止堆栈溢出。 Python（或者更确切地说，CPython 实现）不会优化尾递归，无节制的递归会导致堆栈溢出。您可以使用 sys.getrecursionlimit：

import sys
print(sys.getrecursionlimit())

并使用 sys.setrecursionlimit 更改递归限制：

sys.setrecursionlimit(1500)

但这样做是危险的——标准限制有点保守，但 Python 堆栈框架可能相当大。

Python 不是一种函数式语言，尾递归也不是一种特别有效的技术。如果可能的话，迭代地重写算法通常是一个更好的主意。

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn't optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimit:

import sys
print(sys.getrecursionlimit())

and change the recursion limit with sys.setrecursionlimit:

sys.setrecursionlimit(1500)

but doing so is dangerous -- the standard limit is a little conservative, but Python stackframes can be quite big.

Python isn't a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

回复 原文
感悟人生的甜 2024-09-18 21:59:44

看起来您只需要设置更高的递归深度：

import sys
sys.setrecursionlimit(1500)

Looks like you just need to set a higher recursion depth:

import sys
sys.setrecursionlimit(1500)
回复 原文
写给空气的情书 2024-09-18 21:59:44

如果您经常需要更改递归限制（例如，在解决编程难题时），您可以定义一个简单的 上下文管理器如下所示：

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 语句主体退出时，递归限制将恢复为默认值。

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

If you often need to change the recursion limit (e.g. while solving programming puzzles) you can define a simple context manager like this:

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)

Then to call a function with a custom limit you can do:

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

On exit from the body of the with statement the recursion limit will be restored to the default value.

P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.

回复 原文
ま昔日黯然 2024-09-18 21:59:44

这是为了避免堆栈溢出。 Python解释器限制递归的深度，以帮助您避免无限递归，从而导致堆栈溢出。
尝试增加递归限制 (sys.setrecursionlimit) 或在不使用递归的情况下重写代码。

来自 Python 文档：

sys.getrecursionlimit()

返回递归限制的当前值，即Python解释器堆栈的最大深度。此限制可防止无限递归导致 C 堆栈溢出并导致 Python 崩溃。可以通过 setrecursionlimit() 设置.

It's to avoid a stack overflow. The Python interpreter limits the depths of recursion to help you avoid infinite recursions, resulting in stack overflows.
Try increasing the recursion limit (sys.setrecursionlimit) or re-writing your code without recursion.

From the Python documentation:

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

回复 原文
萌辣 2024-09-18 21:59:44

resource.setrlimit 还必须用于增加堆栈大小并防止段错误

Linux 内核 限制进程堆栈。

Python将局部变量存储在解释器的堆栈上，因此递归会占用解释器的堆栈空间。

如果 Python 解释器尝试超过堆栈限制，Linux 内核会使其出现分段错误。

堆栈限制大小由 getrlimit 和 setrlimit 系统调用控制。

Python 通过 resource 模块提供对这些系统调用的访问。

sys.setrecursionlimit 例如在 https://stackoverflow.com/a/3323013/895245 中提到仅仅增加了Python解释器自身对其自身堆栈大小施加的限制，但并没有触及Linux内核对Python进程施加的限制。

示例程序：

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

当然，如果你不断增加 setrlimit，你的 RAM 最终会耗尽，这会导致你的计算机因交换疯狂而停止运行，或者通过 OOM 杀手。

在 bash 中，您可以使用以下命令查看并设置堆栈限制（以 kb 为单位）：

ulimit -s
ulimit -s 10000

我的默认值是 8Mb。

另请参阅：

在 Ubuntu 16.10、Python 2.7.12 上测试。

resource.setrlimit must also be used to increase the stack size and prevent segfault

The Linux kernel limits the stack of processes.

Python stores local variables on the stack of the interpreter, and so recursion takes up stack space of the interpreter.

If the Python interpreter tries to go over the stack limit, the Linux kernel makes it segmentation fault.

The stack limit size is controlled with the getrlimit and setrlimit system calls.

Python offers access to those system calls through the resource module.

sys.setrecursionlimit mentioned e.g. at https://stackoverflow.com/a/3323013/895245 only increases the limit that the Python interpreter self imposes on its own stack size, but it does not touch the limit imposed by the Linux kernel on the Python process.

Example program:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

Of course, if you keep increasing setrlimit, your RAM will eventually run out, which will either slow your computer to a halt due to swap madness, or kill Python via the OOM Killer.

From bash, you can see and set the stack limit (in kb) with:

ulimit -s
ulimit -s 10000

The default value for me is 8Mb.

See also:

Tested on Ubuntu 16.10, Python 2.7.12.

回复 原文
陪你到最终 2024-09-18 21:59:44

使用保证尾部调用优化的语言。或者使用迭代。或者，使用装饰器变得可爱。

Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.

回复 原文
捶死心动 2024-09-18 21:59:44

我意识到这是一个老问题，但对于那些阅读的人来说，我建议不要使用递归来解决此类问题 - 列表速度更快并且完全避免递归。我将其实现为：（

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])

如果您从 0 而不是 1 开始计算斐波那契数列，请在 xrange 中使用 n+1。）

I realize this is an old question but for those reading, I would recommend against using recursion for problems such as this - lists are much faster and avoid recursion entirely. I would implement this as:

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])

(Use n+1 in xrange if you start counting your fibonacci sequence from 0 instead of 1.)

回复 原文
慈悲佛祖 2024-09-18 21:59:44

我遇到了类似的问题，错误为“超出最大递归深度”。我发现该错误是由我使用 os.walk 循环的目录中的损坏文件触发的。如果您在解决此问题时遇到困难并且正在使用文件路径，请务必缩小范围，因为它可能是损坏的文件。

I had a similar issue with the error "Max recursion depth exceeded". I discovered the error was being triggered by a corrupt file in the directory I was looping over with os.walk. If you have trouble solving this issue and you are working with file paths, be sure to narrow it down, as it might be a corrupt file.

回复 原文
水溶 2024-09-18 21:59:44

当然，斐波那契数可以通过应用 Binet 公式：

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) 的所有值（直到该值）。

Of course Fibonacci numbers can be computed in O(n) by applying the Binet formula:

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))

As the commenters note it's not O(1) but O(n) because of 2**n. Also a difference is that you only get one value, while with recursion you get all values of Fibonacci(n) up to that value.

回复 原文
冰雪之触 2024-09-18 21:59:44

如果只想得到几个斐波那契数列，可以使用矩阵法。

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

它的速度很快，因为 numpy 使用快速求幂算法。您可以在 O(log n) 内得到答案。它比比奈公式更好，因为它只使用整数。但如果你想要n以内的所有斐波那契数，那么最好通过记忆来完成。

If you want to get only few Fibonacci numbers, you can use matrix method.

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

It's fast as numpy uses fast exponentiation algorithm. You get answer in O(log n). And it's better than Binet's formula because it uses only integers. But if you want all Fibonacci numbers up to n, then it's better to do it by memorisation.

回复 原文
仅此而已 2024-09-18 21:59:44

我们可以使用 @lru_cache 装饰器和 setrecursionlimit() 方法来做到这一点：

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

输出

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

源

functools lru_cache

We can do that using @lru_cache decorator and setrecursionlimit() method:

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

Output

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Source

functools lru_cache

回复 原文
夏有森光若流苏 2024-09-18 21:59:44

RecursionError: 比较中超出最大递归深度

解决方案：

首先，最好知道当您在 Python 中对大输入（> 10^4）执行递归函数时，您可能会遇到“超出最大递归深度错误”。

Python 中的 sys 模块有一个函数 getrecursionlimit() 可以显示您的 Python 版本中的递归限制。

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

Python 的某些版本中的默认值为 1000，而其他版本中的默认值为 1500。

您可以更改此限制，但重要的是要知道如果将其增加太多，则会出现内存溢出错误。

所以增加之前要小心。您可以在 Python 中使用 setrecursionlimit() 来增加此限制。

import sys
sys.setrecursionlimit(3000)

请点击此链接了解有关导致此问题的原因的更多信息：

https://elvand.com/quick -排序二进制搜索/

RecursionError: maximum recursion depth exceeded in comparison

Solution :

First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.

The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

The default in some version of Python is 1000 and in some other it was 1500

You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.

So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.

import sys
sys.setrecursionlimit(3000)

Please follow this link for more information about somethings cause this issue :

https://elvand.com/quick-sort-binary-search/

回复 原文
从﹋此江山别 2024-09-18 21:59:44

正如 @alex 建议，您可以使用 生成器函数 按顺序而不是递归地执行此操作。

这是您问题中的等效代码：

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error

As @alex suggested, you could use a generator function to do this sequentially instead of recursively.

Here's the equivalent of the code in your question:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error
回复 原文
忆伤 2024-09-18 21:59:44

编辑：6年后，我意识到我的“使用生成器”是轻率的并且没有回答问题。抱歉。

我想我的第一个问题是：您真的需要更改递归限制吗？如果不是，那么也许我的或任何其他不涉及更改递归限制的答案都将适用。否则，如上所述，使用 sys.getrecursionlimit(n) 覆盖递归限制。

使用发电机？

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

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

以上 fib() 函数改编自 Python 生成器简介。

Edit: 6 years later I realized my "Use generators" was flippant and didn't answer the question. My apologies.

I guess my first question would be: do you really need to change the recursion limit? If not, then perhaps my or any of the other answers that don't deal with changing the recursion limit will apply. Otherwise, as noted, override the recursion limit using sys.getrecursionlimit(n).

Use generators?

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

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

Above fib() function adapted from Introduction to Python Generators.

回复 原文
不再见 2024-09-18 21:59:44

许多人建议增加递归限制是一个很好的解决方案，但这并不是因为总会有限制。相反，使用迭代解决方案。

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

Many recommend that increasing recursion limit is a good solution however it is not because there will be always limit. Instead use an iterative solution.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)
回复 原文
看轻我的陪伴 2024-09-18 21:59:44

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

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))

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

I wanted to give you an example for using memoization to compute Fibonacci as this will allow you to compute significantly larger numbers using recursion:

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))

This is still recursive, but uses a simple hashtable that allows the reuse of previously calculated Fibonacci numbers instead of doing them again.

回复 原文
飘然心甜 2024-09-18 21:59:44
import sys
sys.setrecursionlimit(1500)

def fib(n, sum):
    if n < 1:
        return sum
    else:
        return fib(n-1, sum+n)

c = 998
print(fib(c, 0))

import sys
sys.setrecursionlimit(1500)

def fib(n, sum):
    if n < 1:
        return sum
    else:
        return fib(n-1, sum+n)

c = 998
print(fib(c, 0))
回复 原文
灼痛 2024-09-18 21:59:44

我不确定我是否在重复某人，但前段时间，一些好心人为递归调用函数编写了 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

实际上是数字的音调）

I'm not sure I'm repeating someone but some time ago some good soul wrote Y-operator for recursively called function like:

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

and then recursive function needs form:

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)

for Fibonacci numbers your function looks like this:

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))

output:

..684684301719893411568996526838242546875

(actually tones of digits)

回复 原文
迷路的信 2024-09-18 21:59:44

我们还可以使用动态编程自下而上方法的变体

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))

We could also use a variation of dynamic programming bottom up approach

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))
回复 原文
~没有更多了~

关于作者

叹沉浮

暂无简介

0 文章
0 评论
624 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

淡笑忘祈一世凡恋

文章 0 评论 0

我们的影子

文章 0 评论 0

素年丶

文章 0 评论 0

南笙

文章 0 评论 0

18215568913

文章 0 评论 0

qq_xk7Ean

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文