I\'m trying to solve Fibonacci on the stack - I understand the concept but I can
ID: 3632282 • Letter: I
Question
I'm trying to solve Fibonacci on the stack - I understand the concept but I cannot figure out what is wrong with my code. I'm using an if loop so as long as the value of n is greater than 1 then it knows to continue calculating the Fibonacci. I'm thinking of it as a tree where you start with say Fib(4) then the stack will branch down to fib(3) + fib(2) and so on. Below is my code, I would appreciate it if someone could help me figure out what my logic that I'm messing up on to solve the Fibonacci of any number on the stack.Thank you in advance!
unsigned long long fibStack( unsigned long long num )
{
unsigned long long x = 0;
unsigned long long sx = 0;
typeStack *pStack = fnCreateStack();
typeStackData *pData, *pPop;
pData = (typeStackData *)malloc( sizeof(typeStackData));
pData->llInput = num;
pData->sx = sx;
vdPush( pStack, pData );
llCount ++;
while ( !fnEmptyStack(pStack) ) {
pPop = fnPop( pStack );
if ( pData->llInput > 1 || pData->sx > 1 ){
pData = (typeStackData *)malloc( sizeof(typeStackData));
pData->llInput = pPop->llInput - 1;
pData->sx = pPop->llInput - 2 ;
printf( "Push Number: %llu; Stack Fibonacci: %llu; Fibonacci: %llu ", pData->llInput, pData->sx, x);
vdPush( pStack, pData );
llCount ++;
} else {
x=x+pData->llInput;
}
free ( pPop );
}
free ( pStack );
return ( x );
}
Explanation / Answer
Unless there's a requirement you're not listing to use your own stack, then make use of the computer's and solve it recursively. here's and example, in c, and only using longs.
#include <stdlib.h>
long fib(long x) {
if (x < 1) {
return 0;
else if (x == 1) {
return 1;
} else {
return fib(x-1)+fib(x-2);
}
}
int main() {
printf("Fib(5)=%ld ", fib(5));
}