My C code for Fibonacci Sequence

Question

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[3];  //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[100];

    // 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....

Answer 1

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[0] and [1] to take care of special cases.
    static unsigned int fibResult[FIBMAX] = { 1, 1 };

    // Guard against bad input.
    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;
}