def fib(n):
def fibt(a, b, n):
if n <= 1:
return b
else:
return fibt(b, a + b, n - 1)
if n == 0:
return 0
else:
return fibt(0, 1, n);
and can memoization speed up this even more? tesintg with memoization
doesnt really say anything because it is so fast it is instant anyway.
(the classic easy-redable exponential fib-function can obv be helped
enormously with memoization though.) 6 1228
ssecorp <ci**********@gmail.comasked:
Why is this blowing the stack, thought it was tail-recursive...
Because python does no tail-call optimization.
Ciao
Marc
ssecorp wrote:
<a recursive Fibonacci generator thast demonstrates no tail recursion
used>
and can memoization speed up this even more? ....
Generators get you to an even clearer Fibonacci expression.
def _Fibonacci_gen():
a, b = 1, 0
while True:
a += b
yield a
b += a
yield b
Here's how to use it to avoid redundant comutation:
_next_entry = _Fibonacci_gen().next
_sofar = []
def fib(n):
while len(_sofar) <= n:
_sofar.append(_next_entry())
return _sofar[n]
--Scott David Daniels Sc***********@Acm.Org
ssecorp wrote:
def fib(n):
def fibt(a, b, n):
if n <= 1:
return b
else:
return fibt(b, a + b, n - 1)
if n == 0:
return 0
else:
return fibt(0, 1, n);
and can memoization speed up this even more? tesintg with memoization
doesnt really say anything because it is so fast it is instant anyway.
Except for the fact that a+b gets slower as a and b get bigger, this
would already be linear time in n. Memoization (here by means of a
linear list) only helps if the list is preserved and one makes repeated
requests for various fib values.
I am just curious what input you tried that blew the stack? It had to
be pretty large.
The stack problem, by the way, is one reason linear induction is usually
written in Python with iteration syntax instead of recursion syntax.
Another is the extra simplicity.
def fib(n):
a,b = 1,0
while n:
a,b,n = b, a+b, n-1
return b
A third is the ease of conversion to a (space-efficient) generator function.
def fib_gen()
a,b = 1,0
while True:
yield b
a,b = b, a+b
The generator it produces can be used, for instance, to fill a list
(linear memo) 'on demand'.
A model that leads to the linear algorithm (as opposed to the double
recursion derived from Fibonacci's rabbit model) is as follows:
A population consists of juveniles and adults. In one period, juveniles
become adults (which never die) and adults birth (or bud off) one
juvenile. (Yeast are somewhat like this.) At time 0, we start with 1
juvenile and 0 adults. How many adults are there at time n?
Terry Jan Reedy
On Sat, 12 Jul 2008 19:25:18 -0400, Terry Reedy wrote:
ssecorp wrote:
>def fib(n): def fibt(a, b, n): if n <= 1: return b else: return fibt(b, a + b, n - 1) if n == 0: return 0 else: return fibt(0, 1, n);
and can memoization speed up this even more? tesintg with memoization doesnt really say anything because it is so fast it is instant anyway.
Except for the fact that a+b gets slower as a and b get bigger, this
would already be linear time in n. Memoization (here by means of a
linear list) only helps if the list is preserved and one makes repeated
requests for various fib values.
I am just curious what input you tried that blew the stack? It had to
be pretty large.
No, not really. Try it for yourself: on my system, I get RuntimeError:
maximum recursion depth exceeded with fib(999).
fib(999) is a large number, with 208 digits, but not that large:
26863810024485359386146727202142923967616609318986 9523401
23175997617981700247881689338369654483356564191827 8561614
43356312976673642210350324634850410377680367334151 1728991
69723197082763985615764450078474174626L
--
Steven
On Jul 13, 7:56*am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.auwrote:
On Sat, 12 Jul 2008 19:25:18 -0400, Terry Reedy wrote:
ssecorp wrote:
def fib(n):
* * def fibt(a, b, n):
* * * * if n <= 1:
* * * * * * return b
* * * * else:
* * * * * * return fibt(b, a + b, n - 1)
* * if n == 0:
* * * * return 0
* * else:
* * * * return fibt(0, 1, n);
and can memoization speed up this even more? tesintg with memoization
doesnt really say anything because it is so fast it is instant anyway.
Except for the fact that a+b gets slower as a and b get bigger, this
would already be linear time in n. *Memoization (here by means of a
linear list) only helps if the list is preserved and one makes repeated
requests for various fib values.
I am just curious what input you tried that blew the stack? *It had to
be pretty large.
No, not really. Try it for yourself: on my system, I get RuntimeError:
maximum recursion depth exceeded with fib(999).
fib(999) is a large number, with 208 digits, but not that large:
26863810024485359386146727202142923967616609318986 9523401
23175997617981700247881689338369654483356564191827 8561614
43356312976673642210350324634850410377680367334151 1728991
69723197082763985615764450078474174626L
--
Steven
The default CPython recursion limit is 1000 - so hitting it with an
input of 999 is not that surprising...
You can set a higher limit with sys.setrecursionlimit(...)
Michael Foord http://www.ironpythoninaction.com/
On Jul 13, 8:44*pm, Fuzzyman <fuzzy...@gmail.comwrote:
On Jul 13, 7:56*am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.auwrote:
On Sat, 12 Jul 2008 19:25:18 -0400, Terry Reedy wrote:
ssecorp wrote:
>def fib(n):
>* * def fibt(a, b, n):
>* * * * if n <= 1:
>* * * * * * return b
>* * * * else:
>* * * * * * return fibt(b, a + b, n - 1)
>* * if n == 0:
>* * * * return 0
>* * else:
>* * * * return fibt(0, 1, n);
>and can memoization speed up this even more? tesintg with memoization
>doesnt really say anything because it is so fast it is instant anyway.
Except for the fact that a+b gets slower as a and b get bigger, this
would already be linear time in n. *Memoization (here by means of a
linear list) only helps if the list is preserved and one makes repeated
requests for various fib values.
I am just curious what input you tried that blew the stack? *It hadto
be pretty large.
No, not really. Try it for yourself: on my system, I get RuntimeError:
maximum recursion depth exceeded with fib(999).
fib(999) is a large number, with 208 digits, but not that large:
26863810024485359386146727202142923967616609318986 9523401
23175997617981700247881689338369654483356564191827 8561614
43356312976673642210350324634850410377680367334151 1728991
69723197082763985615764450078474174626L
--
Steven
The default CPython recursion limit is 1000 - so hitting it with an
input of 999 is not that surprising...
You can set a higher limit with sys.setrecursionlimit(...)
Though that would be a kludge, not a fix. Using iteration or generator
expression is better. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Rodrigo Benenson |
last post by:
Hi,
I need to implement a stack on a file.
The idea is to have a big list, and put part of his head on the disk. The
model of access to the file is like a stack (read in order only the tail,...
|
by: atv |
last post by:
Hi,
is there something wrong with this code? It seems that it crashes
at the else { clause, when allocating a second record. Excuse for
the indentation, the g_warnings are from gtk.
Also, i'm...
|
by: Aris |
last post by:
Hello!
This is my problem.
I'm trying to make an inorder traversal algorithm for
a binary tree, not a recursive one, but using a stack.
Till now I got this:
void traverse(tree * p)
{
l:...
|
by: Aris |
last post by:
Hello!
Im trying to implement a queue
using a linked list.
I've made that code
and I expected my Degueue()
function to return the value of the
key of the node I constructed.
But It does not....
|
by: babynailah |
last post by:
This is what i have to do and this is all i have....
HELP ME PLEASE MY GRADE IN CLASS DEPENDS ON IT!!!!
Your problem is to simulate certain aspects of a cell phone. The following features are...
|
by: softwindow |
last post by:
#include "stdio.h"
#include "malloc.h"
struct student{
int age;
char *nms;
struct student *next;
};
struct student *create(){
int ags=0,size=sizeof(struct student);
char *nms=" ";
|
by: Chad |
last post by:
say my input file is
$ more suck
______
< gnu? >
------
\ , ,
\ /( )`
\ \ \___ / |
/- _ `-/ '
|
by: Owen Zhang |
last post by:
What is the best way to implement "tail -f" in C or C++ and higher
performance compared to either unix shell command "tail -f" or perl
File::Tail ? Any suggestion appreciated. Thanks.
|
by: ssecorp |
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
so I try it and when I run:
@Decorators.tail_recursion
def fibtr(n):
def fibt(a, b, n):
if n <= 1:
return b
else:
return...
|
by: Muzammil |
last post by:
int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n-1)+1/n;
}
}
can any help me ??
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| | |