Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #4433
| From | Terry Reedy <tjreedy@udel.edu> |
|---|---|
| Subject | Re: Fibonacci series recursion error |
| Date | 2011-05-01 22:30 -0400 |
| 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> <ipgaej$ma5$1@solani.org> <4dbbb7b6$0$29991$c3e8da3$5496439d@news.astraweb.com> <ipkpkf$7g7$1@dont-email.me> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1053.1304303413.9059.python-list@python.org> (permalink) |
On 5/1/2011 7:16 PM, BartC wrote: > Yes, it generates lots of calls. > > About 22000 for fib(20), and 330 million for fib(40). Using the standard double recursion implementation of fib, ncf(n) (number of calls to fib() for fib(n)) requires ncf(n-2) + ncf(n+1) + 1 calls. The +1 is for the call to fib(n) itself). So it grows a bit faster than fib(n). Fib(n) is actually calculated as the sum of fib(n) 1s: 1+1+1....+1 fib(n) times as 1 is the only non-0 base case and there is nothing else added or multiplied in non-base cases. To put it another way, there are fib(n) leaf nodes labeled 1 in the unbalanced tree generated by the recursion. -- Terry Jan Reedy
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-04-30 07:18 +0000
Re: Fibonacci series recursion error "BartC" <bc@freeuk.com> - 2011-05-02 00:16 +0100
Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-01 22:30 -0400
Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 01:27 -0700
Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 08:56 +0000
Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 10:53 +0100
Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 03:40 -0700
Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 16:24 +0000
Re: Fibonacci series recursion error Mark Dickinson <dickinsm@gmail.com> - 2011-05-02 14:18 -0700
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 19:03 +1000
Re: Fibonacci series recursion error Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-05 14:35 +1200
csiph-web