# My C code for Fibonacci Sequence

I've been learning more programming in the past few years (C, Java, Arduino) for my hobbies. I read the "C for Dummies" book and found that it was good, but did not cover much - especially pointers... One of my friends from college (CS major) suggested a simple program exercise to see if I could figure out how to use pointers. Well, I had to refer to a pdf of Ritchie's text "The C Programming Language" to learn about pointers. He asked me to make a program that returns the Fibonacci sequence. A month or so ago, I sent him my program, but he hasn't had time to review it since he is very busy with work these days. Basically what I am wondering about my program is if it is redundant or "too verbose" - basically is it written efficiently? IMO, as a hobbyist programmer, it works just fine.

Below is the source code file he initially sent to me:

/**

* @file  fibonacci.cpp
*
* @brief Prints out a partial Fibonacci sequence.

*/

#include <stdio.h>

// Function prototype for fibonacci()
unsigned int Fibonacci(unsigned int);

int main(int argc, char** argv)
{
printf("Fibonacci Sequence:\n");

for (unsigned int n = 0; n < 10; ++n)
{
unsigned int fib = Fibonacci(n);
printf("%d ", fib);
}

return 0;
}

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int N)
{
// Actual implementation goes here!!
}


Below is my version of the program that I sent to him for review:

/**

* @file  fibonacci.cpp
*
* @brief Prints out a partial Fibonacci sequence.

*/

#include <stdio.h>
unsigned int n;
char nMax;  //user input for sequence up to and including value @ this index
int Nmax;

// Function prototype for fibonacci()
unsigned int Fibonacci(unsigned int);

int main(int argc, char** argv)
{
printf("Please input the Nth index of the last sequence value.\n");
printf("Program will return entire Fibonacci Sequence up to and including Nth value.\n");

gets(nMax);
Nmax =atoi(nMax);

for (n = 0; n < Nmax; ++n)
{
unsigned int fib = Fibonacci(n);
printf("%d ", fib);
}

return 0;
}

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int n)
{
// Actual implementation goes here!!

unsigned int N;  //function output value

//declare a temp array of sequence values
unsigned int tempseq;

// declare two ptrs
unsigned int *prev;  //pointer to previous or (n-1) value in sequence
unsigned int *prevprev;  //pointer to previous previous or (n-2) value in sequence

if (n==0)
{   N = 1;  //1st seed value
tempseq[n] = N;
}
else if(n==1)
{
N = 1;  //2nd seed value
tempseq[n] = N;
}
else
{
prev = &tempseq[n-1];        //prev ptr points to n-1 array element
prevprev = &tempseq[n-2];    //prevprev ptr points to n-2 array element

N = *prev + *prevprev;       //fibonacci recurrence relation
tempseq[n] = N;              //add current value of N to the temp array

}

return N;

}


EDIT: Not to step on the toes of JS1 who recently replied, but I wanted to add an image here of my cmd line execution of my fibonacci.exe program to show that at least on my pc, it seems to work.... • You could just use the closed form. – user1149 Mar 28 '16 at 19:38
• @BarryCarter What do you mean by 'closed form' ? – PhilosophStein Mar 29 '16 at 14:09
• en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression (sorry, meant to include that earlier). See also the section immediately following the section I linked. – user1149 Mar 29 '16 at 14:29
• @BarryCarter Thanks for the link, I will look at it soon. Do you have any ideas why my code did not work for JS1 (who posted an answer below), but it does 'work' for me when I run my program in the windows cmd line? I did not fully read through JS1's answer yet because I feel it is important to first understand why my program apparently works for me... – PhilosophStein Mar 29 '16 at 15:07
• The unsigned ints make me curious, but I don't think they should cause a problem. – user1149 Mar 29 '16 at 18:04

### Doesn't work

The program doesn't work for me. Example:

\$ ./fibonacci
Please input the Nth index of the last sequence value.
Program will return entire Fibonacci Sequence up to and including Nth value.
10
1 1 2 3 1 0 1 1 2 3


The problem is that the array tempseq is a temporary local variable, which means that every time you call the function Fibonacci(), that variable becomes unitialized. Your code is doing two things wrong:

1. It assumes that tempseq will contain the values that it had from previous invocations of the function Fibonacci().
2. It assumes that Fibonacci() will be called in a loop from 0 to n. If you just called Fibonacci(10) directly, it would not work because it depends on the answers for 8 and 9 being precomputed.

### Fixes

• To fix problem #1, you can declare your tempseq array using the static keyword. This makes the array persist across invocations. You can think of it like if the static keyword made the tempseq variable into a global variable.

• To fix problem #2, you should not assume that an entry in tempseq is necessarily valid. You can do something like check if the entry is 0. If it is zero, then the entry must be computed, otherwise it is valid to use.

### Rewrite

I have rewritten your function with the two problems fixed:

#define FIBMAX        100

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int n)
{
// FibResult is a persistent array of already computed values.
// We initialize fibResult and  to take care of special cases.
static unsigned int fibResult[FIBMAX] = { 1, 1 };

if (n >= FIBMAX)
return 0;

if (fibResult[n] == 0) {
// We have not previously computed this entry, so compute it now
// using the recurrence relation.
//
// Note: calling Fibonacci(n-1) guarantees that fibResult[n-2] will
// be set, so we just use that to avoid one function call.  We
// could have written this and it would have worked just fine:
//
// fibResult[n] = Fibonacci(n-1) + Fibonacci(n-2);
//
fibResult[n] = Fibonacci(n-1) + fibResult[n-2];
}

return fibResult[n];
}


This rewrite also:

1. Replaces the magic number 100 with a defined constant and checks the input so that we don't have any buffer overflow problems.
2. Takes care of the special cases of n=0 and n=1 by filling in those entries in the fibResult array.

### Simpler way

You might also want to consider a simpler function that doesn't use an array of precomputed values. Calculating a fibonacci number can be done in a simple loop like this:

unsigned int Fibonacci(unsigned int n)
{
unsigned int f1 = 1;
unsigned int f2 = 1;

for (unsigned int i = 0; i < n; i++) {
f2 = f1 + f2;
f1 = f2 - f1;
}
return f1;
}

• The program may not work for you, but can you explain why it seemingly worked for me when I ran it from the windows cmd line? – PhilosophStein Mar 29 '16 at 14:10
• @PhilosophStein Because whatever compiler you used placed the temporary array someplace on the stack where the call to printf() did not happen to clobber it. If you really want to know the answer, you'll need to understand where local variables are stored (on the stack), and how the stack works when you call into a function. – JS1 Mar 29 '16 at 17:36
• At JS1 (since I cannot seem to be able to reply directly to your user name...): thanks for providing that explanation. I see that you did not even need to use pointers to accomplish the goal of the program! – PhilosophStein Apr 2 '16 at 13:57