Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #4505
| Path | csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail |
|---|---|
| Return-Path | <rosuav@gmail.com> |
| X-Original-To | python-list@python.org |
| Delivered-To | python-list@mail.python.org |
| X-Spam-Status | OK 0.004 |
| X-Spam-Evidence | '*H*': 0.99; '*S*': 0.00; 'operator': 0.05; 'closer': 0.07; 'function,': 0.07; 'all).': 0.09; 'block.': 0.09; 'conditional': 0.09; 'recursion': 0.09; 'stack,': 0.09; 'exception': 0.12; 'subject:error': 0.12; 'def': 0.13; 'am,': 0.14; 'wrote:': 0.14; 'head,': 0.16; 'overflow': 0.16; 'stack': 0.16; 'tue,': 0.20; 'header:In-Reply-To:1': 0.22; 'keeps': 0.24; '(not': 0.24; 'pointed': 0.25; 'chris': 0.27; 'message- id:@mail.gmail.com': 0.28; "doesn't": 0.28; 'changing': 0.29; 'this.': 0.30; 'depth': 0.31; 'called': 0.32; 'to:addr:python- list': 0.32; 'another': 0.32; 'there': 0.35; 'forces': 0.35; 'two': 0.37; 'received:209.85': 0.37; '(to': 0.38; 'received:google.com': 0.38; 'earlier': 0.39; 'active': 0.39; 'to:addr:python.org': 0.39; 'received:209': 0.39; 'header:Received:5': 0.40; '2011': 0.62; 'ever': 0.65; 'double': 0.69; '(n)': 0.84; 'received:209.85.210.174': 0.84; 'received :mail-iy0-f174.google.com': 0.84; 'look.': 0.93; 'on...': 0.93 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type:content-transfer-encoding; bh=doA9X5JFMbiuc9XXQ7TLNC9Pt6+E31OFeZXwR8/W4QA=; b=kw76/6ASEWvxq3l+nuqyRNtpAF7WjQVh8pJ4ypG/xT3tJoqBnNZIYbwanqggh59g/f ODDlQ8CRoHNnD4m/Uw09SrOse21ESObnIWJik0wocYZcnXMZrIzi2uMAp5IMxBCS5CSE 1W3hg//tybt3F9/TABkwK5bD+vyfsKe8YC1/I= |
| DomainKey-Signature | a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=sd6jffgRyck4P5lwpW0cbMj07aMBNQhEa8QXcI1hAapxjSWwWdD2bryYUVZOGzWm+1 leCeZj2JWzJITqpw3DlYb9Hclg8FRPtHafFGbL0hY+rED4WQUOveT2E95DUXkovo95Ui gwgXWCZmIYcoRgWQg53EeyNKb3fzCClRXgrIc= |
| MIME-Version | 1.0 |
| In-Reply-To | <0HFvp.18698$vT3.2042@newsfe06.iad> |
| References | <a78a0ffd-03cc-4540-addb-b8e206d165d5@n2g2000prj.googlegroups.com> <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 | Tue, 3 May 2011 08:17:35 +1000 |
| Subject | Re: Fibonacci series recursion error |
| From | Chris Angelico <rosuav@gmail.com> |
| To | python-list@python.org |
| Content-Type | text/plain; charset=ISO-8859-1 |
| Content-Transfer-Encoding | quoted-printable |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.12 |
| Precedence | list |
| List-Id | General discussion list for the Python programming language <python-list.python.org> |
| List-Unsubscribe | <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe> |
| List-Archive | <http://mail.python.org/pipermail/python-list> |
| List-Post | <mailto:python-list@python.org> |
| List-Help | <mailto:python-list-request@python.org?subject=help> |
| List-Subscribe | <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1081.1304374657.9059.python-list@python.org> (permalink) |
| Lines | 50 |
| NNTP-Posting-Host | 82.94.164.166 |
| X-Trace | 1304374657 news.xs4all.nl 65870 [::ffff:82.94.164.166]:53930 |
| X-Complaints-To | abuse@xs4all.nl |
| Xref | x330-a1.tempe.blueboxinc.net comp.lang.python:4505 |
Show key headers only | View raw
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