Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #4505
| References | (1 earlier) <BANLkTimfNQhdE1ZJwP_HN64WwERtUOtBvw@mail.gmail.com> <mailman.1011.1304141265.9059.python-list@python.org> <vcNup.5316$Du7.1273@newsfe04.iad> <ipgl8i$nbm$1@r03.glglgl.eu> <0HFvp.18698$vT3.2042@newsfe06.iad> |
|---|---|
| Date | 2011-05-03 08:17 +1000 |
| Subject | Re: Fibonacci series recursion error |
| From | Chris Angelico <rosuav@gmail.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1081.1304374657.9059.python-list@python.org> (permalink) |
On Tue, May 3, 2011 at 7:50 AM, harrismh777 <harrismh777@charter.net> wrote:
> They *are not* called one after the other in the sense that there is ever
> only one level of recursion with each call (not at all). Take a closer look.
> Each call to fib() forces a double head, and each of those forces another
> double head (now four), and so on... the recursion depth exception of the
> OP testifies against your theory.
def fib(n):
if n==1:
return n
return fib(n-1)+fib(n-2)
dis.dis(fib)
2 0 LOAD_FAST 0 (n)
3 LOAD_CONST 1 (1)
6 COMPARE_OP 2 (==)
9 JUMP_IF_FALSE 5 (to 17)
12 POP_TOP
3 13 LOAD_FAST 0 (n)
16 RETURN_VALUE
>> 17 POP_TOP
4 18 LOAD_GLOBAL 0 (fib)
21 LOAD_FAST 0 (n)
24 LOAD_CONST 1 (1)
27 BINARY_SUBTRACT
28 CALL_FUNCTION 1
31 LOAD_GLOBAL 0 (fib)
34 LOAD_FAST 0 (n)
37 LOAD_CONST 2 (2)
40 BINARY_SUBTRACT
41 CALL_FUNCTION 1
44 BINARY_ADD
45 RETURN_VALUE
The recursion is in the last block. Note that it calls a function,
then keeps going. It doesn't fork. There are two CALL_FUNCTION
opcodes, called *sequentially*. In terms of the call stack, there is
only ever one of those two calls active at any given time. Also, as
earlier pointed out, the reason for the stack overflow is that fib(2)
will call fib(1) and fib(0), and fib(0) will call fib(-1) and fib(-2),
etc. Changing the operator from == to <= in the conditional return
will solve this.
Chris Angelico
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar
Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600
csiph-web