Nth Fibonacci using pointers in C; recursive and array

I have this code so far. It works and does what I want it to. I'm wondering if I could make it better. I do not really care for user input or any other "finish touches," just want to make the code more efficient and maybe more useful for future projects. Excessive comments are for my personal use, I find it easier to read when I go back to old projects for references and what not. Thanks!

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

void fabonacci(int * fibArr,int numberOfSeries){
    int n;

    //allocate memory size
    fibArr = malloc (sizeof(int) * numberOfSeries);
    //first val, fib = 0
    *fibArr = 0;//100
    fibArr++;
    //second val, fib = 1
    *fibArr = 1;//104
    fibArr++;

    //printing first two fib values 0 and 1
    printf("%i\n%i\n", *(fibArr- 2),*(fibArr- 1));

    //loop for fib arr
    for(n=0;n<numberOfSeries -2;n++,fibArr++){
        //108 looking back at 104 looking back at 100
        //112 looking back at 108 looking back at 104
        *fibArr = *(fibArr-1) + *(fibArr -2);
        //printing fib arr
        printf("%i\n", *fibArr);
    }
}

int main(){
    //can implm user input if want
    int n = 10;
    int *fib;

    //calling 
    fabonacci(fib,n);
}

2 answers

  • answered 2018-02-13 02:21 user3386109

    One way to improve the code is to let the caller create the array, and pass the array to the fibonacci function. That eliminates the need for fibonacci to allocate memory. Note that the caller can allocate/free if desired, or the caller can just declare an array.

    The other improvement is to use array notation inside of the fibonacci function. You may be thinking that the pointer solution has better performance. It doesn't matter. The maximum value for n is 47 before you overflow a 32-bit int, so n is not nearly big enough for performance to be a consideration.

    Finally, the fibonacci function should protect itself from bad values of n. For example, if n is 1, then the function should put a 0 in the first array entry, and not touch any other entries.

    #include <stdio.h>
    
    void fibonacci(int *array, int length)
    {
        if (length > 0)
            array[0] = 0;
        if (length > 1)
            array[1] = 1;
    
        for (int i = 2; i < length; i++)
            array[i] = array[i-1] + array[i-2];
    }
    
    int main(void)
    {
        int fib[47];
        int n = sizeof(fib) / sizeof(fib[0]);
    
        fibonacci(fib, n);
    
        for (int i = 0; i < n; i++)
            printf("fib[%d] = %d\n", i, fib[i]);
    }
    

  • answered 2018-02-13 02:21 HTNW

    Your code is halfway between two possible interpretations and I can't tell which one you meant. If you want fibonacci(n) to just give the nth number and not have any external side effects, you should write it as follows:

    int fibonacci(int n) {
       int lo, hi;
       lo = 0;
       hi = 1;
       while(n-- > 0) {
         int tmp = hi;
         lo = hi;
         hi = lo + tmp;
       }
       return lo;
    }
    

    You need no mallocs or frees because this takes constant, stack-allocated space.

    If you want, instead, to store the entire sequence in memory as you compute it, you may as well require that the memory already be allocated, because this allows the caller to control where the numbers go.

    // n < 0 => undefined behavior
    // not enough space allocated for (n + 1) ints in res => undefined behavior
    void fibonacci(int *res, int n) {
      res[0] = 0;
      if(n == 0) { return; }
      res[1] = 1;
      if(n == 1) { return; }
      for(int i = 2; i <= n; i++) {
        res[i] = res[i-1] + res[i-2];
      }
    }
    

    It is now the caller's job to allocate memory:

    int main(){
      int fib[10]; // room for F_0 to F_9
      fibonacci(fib, 9); // fill up to F_9
    
      int n = ...; // some unknown number
      int *fib2 = malloc(sizeof(int) * (n + 2)); // room for (n + 2) values
      if(fib2 == NULL) { /* error handling */ }
      fibonacci(fib2 + 1, n); // leave 1 space at the start for other purposes.
      // e.g. you may want to store the length into the first element
      fib2[0] = n + 1;
      // this fibonacci is more flexible than before
      // remember to free it
      free(fib2);
    }
    

    And you can wrap this to allocate space itself while still leaving the more flexible version around:

    int *fibonacci_alloc(int n) {
        int *fib = malloc(sizeof(int) * (n + 1));
        if(fib == NULL) { return NULL; }
        fibonacci(fib, n);
        return fib;
    }