Fibonacci sequence in C

I'm very new to C, so pointing out better ways of doing things, errors, bad practices, etc would be optimal at this stage.

Code on GitHub

#include 
#include 

int *calculateFibonacciSequence(int n, int start)
{
  int i;

  // Allocate memory for our fibonacci sequence from the heap
  int *numbers = malloc(sizeof(int) * n);

  // Need to calculate at least one number
  if (n  2) {
    start = atoi(argv[2]);
  }

  // Calculate the sequence
  sequence = calculateFibonacciSequence(n, start);

  // Output the sequence
  if (sequence) {
    printf("%d", sequence[0]);

    for (i = 1; i <= n; i++) {
      printf(",%d", sequence[i]);
    }

    // Newline
    puts("");
  } else {
    puts("Error processing fibonacci sequence");
  }

  // Free memory
  free(sequence);

  return 0;
}

What you did well on:

-
Your program is easy to read.

-
You are allocating memory, even though it is unsafe in certain cases (other answers have addressed this, so I won't cover it).

-
You prepare for some corner cases.

Things you could improve:

-
You are returning 0 when your program runs into a problem (except
in one spot where there are too many parameters being entered).

return 0;

0 is typically the return code for a exiting successfully. If we
run into a problem in our program, we should return something to
indicate we ran into a problem. I prefer to return negative numbers.

return -1;

Also, you should return different numbers for different errors. A user generated error such as malformed input should not return the same error code as an internal error. This makes debugging a lot easier when you are trying to determine the cause of an error.

However, since you are returning an int*, it would be better to return NULL instead. This is what you are doing right now, in a somewhat abnormal way by returning 0. Just return NULL.

return NULL;

-
You should mark ints as unsigned if they are never going to be negative.

unsigned int start;

-
You are not maximizing how many Fibonacci you can produce using only an int, or even an unsigned int. An unsigned int has a maximum value of 2147483647, where a long long unsigned int has a maximum value of 18446744073709551615. That's 8589934562 times larger!

-
Declare i inside of your for loops. This is part of the C99 standard, so you may have to adjust how you compile your program.

for (unsigned int i = 1; i <= n; i++)

-
I don't see the point of the start variable. Unless this is part of some problem you are trying to solve, I would just print the whole sequence. It would cut down on your lines of code a lot as well.

-
The Fibonacci series is a great place to practice recursion.

long long unsigned int fibonacci(long long unsigned int n)
{
   if (n < 2) return n;
   else return (fibonacci(n-1) + fibonacci(n-2));
}

This algorithm here is short, and gets the job done just has you did in less lines of code. We could even shorten it a bit further if we wanted to (with ternary operators).

long long unsigned int fibonacci(long long unsigned int n)
{
    return (n < 2)? n : fibonacci(n-1) + fibonacci(n-2);
}

We have to be careful though to avoid repeating the calculation of results for previously processed inputs; to do this we should use memoization. I've implemented this in my final program.

-
Keep in mind that sometimes recursion will make your algorithm a bit
slower with time-complexity, which can be the case here (depending on your implementation of an iterative solution). Here is the fastest iterative algorithm I could work up (this may still be a bit slower with the pow() function).

long long unsigned int fibonacci(long long unsigned int n)
{
    return (1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n));
}

However, using this method requires the use of doubles, and the return will make an implicit cast that could cause some rounding problems. Therefore, we will round() the result in our final code.

-
You should test if you input is a number, and not some malformed input.

if (scanf("%i", &num) <= 0)
{
    puts("Invalid input.");
    return -1;
}

Final code:

• Iterative: O(1)

#include 
#include 
#include 

long long unsigned int fibonacci(long long unsigned int n)
{
    return round((1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n)));
}

int main(void)
{
    unsigned int num = 0;

    printf("Enter how far to calculate the series: ");
    if (scanf("%i", &num) <= 0)
    {
        puts("Invalid input.");
        return -1;
    }

    for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
}

• Recursion: O(n)

#include 
#include 

#define ARRAYLENGTH 100 // keep in mind the result must fit in an llu int (fibonacci values grow rapidly)
                        // you will run into issues after 93, so set the length at 100
long long int memoization[ARRAYLENGTH];

long long unsigned int fibonacci(long long unsigned int n)
{
    if (memoization[n] != -1) return memoization[n];

    return (n < 2)? n : (memoization[n] = fibonacci(n-1) + fibonacci(n-2));
}

int main(void)
{
    unsigned int num = 0;

    for(unsigned int i = 0; i < ARRAYLENGTH; i++) memoization[i] = -1; // preset array

    printf("Enter how far to calculate the series: ");
    if (scanf("%i", &num) <= 0)
    {
        puts("Invalid input.");
        return -1;
    }
    if (num < ARRAYLENGTH)
    {
        for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
    }
    else
    {
        puts("Input number is larger than the array length.");
        return -2;
    }
}

StackExchange Code Review Q#39066, answer score: 16