Fibonacci recursion using dynamic stacks (HELP)
Author Message
Fibonacci recursion using dynamic stacks (HELP)

I don't seem to be able to solve this simulated recursion of the Fibonacci
fonction, using dynamic stacks to simulate the recursive calls of
a=fibonacci(n-1);b=fibonacci(n-2). Can anyone help??

Tue, 15 Apr 2003 11:50:19 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> I don't seem to be able to solve this simulated recursion of the Fibonacci
> fonction, using dynamic stacks to simulate the recursive calls of
> a=fibonacci(n-1);b=fibonacci(n-2). Can anyone help??

If you're looking for someone to write it for you, you've come to
the wrong place. If you truely only want help, then post the code that
you have so far, and people here will help you fix it. But, again, no
one here is going to do it for you.

--
Clark S. Cox, III

Tue, 15 Apr 2003 13:18:01 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> I don't seem to be able to solve this simulated recursion of the Fibonacci
> fonction, using dynamic stacks to simulate the recursive calls of
> a=fibonacci(n-1);b=fibonacci(n-2). Can anyone help??

--

San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Tue, 15 Apr 2003 14:44:27 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> I don't seem to be able to solve this simulated recursion of the Fibonacci
> fonction, using dynamic stacks to simulate the recursive calls of
> a=fibonacci(n-1);b=fibonacci(n-2). Can anyone help??

The literature is a good place to start. Any good book on algorithms
will show you how stacks work. And most discussions of recursion focus
on the Fibonacci algorithm as a great example of when not to recurse. So
all you have to do is find a good book on algorithms. Sedgewick is
probably the first place to look.

--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

Tue, 15 Apr 2003 17:05:57 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> I don't seem to be able to solve this simulated recursion of the
> Fibonacci fonction, using dynamic stacks to simulate the recursive
> calls of a=fibonacci(n-1);b=fibonacci(n-2). Can anyone help??

You know how to write the function recursively. Copy this and use to

long MM_RecursiveFib(int x)
{
if(x == 0)
return 0;
if( x == 1)
return 1;
else
return MM_RecursiveFib(x-2) + MM_RecursiveFib(x-1);

Quote:
}

To write Non_RecursiveFib, you have to simulate the computer's call
stack, which it uses for recursion.

(Presumably this is what the tutor wants, not a optimised fibonacci
function which starts at one and counts upwards - this is much faster
as there is no duplication of effort. I should also point out that
there is a formula using the golden ration you can use to calculate
arbitrarily large fibonacci numbers quickly).

Since all the functions are the same, no need to store pointers, just
store the parameters.

The function looks something like this

static int stack[1024];       //call stack
static int stacktop;          // stack top

fib(int N)
{
// tricky bit in here.
do
{
Push N -2 on the stack until N becomes 1 or zero
pop N;
push N-1 on the stack until N becomes 1 or zero
pop two numbers
push the result;
}
whilst(stacksize != 1);

Quote:
}

It's quite hard to change a function from code-recursive to data
recrusive. Michael Abrash, who recruits video games programmers, say
that most of his interviewees fail this particular test.

Sent via Deja.com http://www.deja.com/

Tue, 15 Apr 2003 17:03:40 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> And most discussions of recursion focus on the Fibonacci algorithm
> as a great example of when not to recurse. So
> all you have to do is find a good book on algorithms. Sedgewick is
> probably the first place to look.

This should be of interest to the OP though it would be a cheating
implementation, since it doesn't use recursion at all.

long MM_Fibonacci(int x)
{
double tau;
double tau2;
double A;
double B;

tau = (1.0 + sqrt(5.0))/2.0;
tau2 = (1.0 - sqrt(5.0))/2.0;
A = 1.0/sqrt(5.0);
B = -A;

return (long) ( A * pow(tau, (double) x) + B * pow(tau2, (double)
x) );

Quote:
}

Is there anyway of optimising those pow s ?

Sent via Deja.com http://www.deja.com/

Wed, 16 Apr 2003 00:07:31 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> This should be of interest to the OP though it would be a cheating
> implementation, since it doesn't use recursion at all.

> long MM_Fibonacci(int x)
> {
>   double tau;
>   double tau2;
>   double A;
>   double B;

>   tau = (1.0 + sqrt(5.0))/2.0;
>   tau2 = (1.0 - sqrt(5.0))/2.0;
>   A = 1.0/sqrt(5.0);
>   B = -A;

>   return (long) ( A * pow(tau, (double) x) + B * pow(tau2, (double)
> x) );

> }

> Is there anyway of optimising those pow s ?

Yes. Leave the second one out:

unsigned long fib(unsigned x)
{
return (unsigned long) (pow((1.0+sqrt(5))/2,x)/sqrt(5)+0.5);

Quote:
}

(To reach me, replace my middle name with my first.)
--
Brian Blank                           You cannot program
Department of Mathematics              a crooked machine
Washington University in St. Louis      to go straight.
St. Louis, MO 63130                      -Edsger Dijkstra

Mon, 21 Apr 2003 15:54:14 GMT
Fibonacci recursion using dynamic stacks (HELP)

Quote:

> > This should be of interest to the OP though it would be a cheating
> > implementation, since it doesn't use recursion at all.
> > [...]

Here is one which is recursive downwards,
using only a logarithmic number of recursive call.

\$ a.out 30
fibo (1, 2)= (1, 1)
fibo (3, 4)= (2, 3)
fibo (7, 8)= (13, 21)
fibo (15, 16)= (610, 987)
fibo (30, 31)= (832040, 1346269)
fibo (30)= 832040
\$

Regis

------------------------------------

#include <stdlib.h>
#include <stdio.h>

void fibo_odd_even (long o, long* fo, long* fe);
void fibo_even_odd (long e, long* fe, long* fo);
void fibo          (long n, long* fn, long* fm);

void fibo_odd_even (long o, long* fo, long* fe) {
long fn, fm, n= (o-1)/2;
fibo (n, & fn, & fm);
*fo=   fn*fn + fm*fm;
*fe= 2*fn*fm + fm*fm;

Quote:
}

void fibo_even_odd (long e, long* fe, long* fo) {
long fn, fm, n= e/2;
fibo (n, & fn, & fm);
*fe= 2*fn*fm - fn*fn;
*fo=   fn*fn + fm*fm;

Quote:
}

void fibo (long n, long* fn, long* fm) {
if      (n     == 0) { *fn= 0; *fm= 1; }
else if (n     == 1) { *fn= 1; *fm= 1; }
else if (n % 2 == 0) fibo_even_odd (n, fn, fm);
else                 fibo_odd_even (n, fn, fm);
printf ("fibo (%li, %li)= (%li, %li)\n", n, n+1, *fn, *fm);

Quote:
}

int main (int argc, char* argv []) {
long n, fn, fm;
if (argc != 2) {
fprintf (stderr, "usage: %s rank\n", argv [0]);
return EXIT_FAILURE;
}
n= atoi (argv [1]);
fibo (n, & fn, & fm);
printf ("fibo (%li)= %li\n", n, fn);
return EXIT_SUCCESS;
Quote:
}

Mon, 21 Apr 2003 21:07:10 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages