Fibonacci sequence in C

Question

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 <stdio.h>
#include <stdlib.h>

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 <= 0) {
    return 0;
  }

  // Can't start with a number under zero
  if (start != 0 && start != 1) {
    return 0;
  }

  // Get the seed values
  if (start == 0) {
      numbers[0] = 0;
      numbers[1] = 1;
  } else {
      numbers[0] = 1;
      numbers[1] = 1;
  }

  // Calculate the sequence
  for (i = 1; i < n; i++) {
    numbers[i + 1] = numbers[i] + numbers[i - 1];
  }

  return numbers;
}

int main(int argc, char *argv[])
{
  int i, n;
  int start = 0;
  int *sequence;

  // Check to see how many arguments we got
  if (argc <= 1) {
    puts("Please pass the number of iterations to run.");
    return 1;
  }

  // Get the number of iterations to run
  n = atoi(argv[1]);

  // Did they specify a start value
  if (argc > 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;
}

Answer 1

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 <stdio.h>
  #include <stdlib.h>
  #include <math.h>
  
  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 <stdio.h>
  #include <stdlib.h>
  
  #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;
      }
  }
  

Answer 2

You C is very good. Just a few comments:

The start parameter is pointless. Just print the whole sequence.

Don't allocate memory until you know your parameters are valid. Else you have a memory leak.

You don't check that the numbers[] array was allocated successfully and you have overflowed the array by one place.

Define loop variables in the loop where possible:

for (int i = 1; i < n; i++) {...}

Many of your comments are not useful. They might be required by your supervisor (if you have one) but in normal code would be considered 'noise'. Comments should add something that the reader can't see for himself. Usually 'why' is a better question to answer than 'what', as for good code, what you are doing should be self-evident.

Defining variables where they are needed, not at the beginning of functions, is often considered best practice.

EDIT: Also, to add a new line, putchar('\n'); would be more normal.

Answer 3

Your code is rather unsafe.

You allocate memory using malloc(), based on a user-submitted number that is never checked. If the user supplies -1 in argv[1], malloc() will try to allocate 0xFFFFFFFC bytes on a 32- or 0xFFFFFFFFFFFFFFFC bytes on a 64-bit two's-complement architecture. This may fail.

The return value of malloc() is never checked, which may lead to a segmentation-fault if malloc() failed and the resulting null-pointer is subsequently dereferenced.

After you allocate your buffer, you check for input validity, and if the check fails, the function returns 0. main() treats this return value as a pointer and free()'s it, but if an error occurred in the function, 0 is passed to free() instead of the pointer to the allocation and the allocated memory is leaked.

In this case it doesn't matter, because the program exits and all memory is automatically freed on program exit, but for a bigger project this would not work.

The code should be rewritten.

Answer 4

Welcome to the world of C and its pitfalls.

In particular, you have a memory leak if the parameters to calculateFibonacciSequence() fail validation. That is, you call malloc(), but the numbers pointer will be lost forever once you return 0. The solution would be to postpone malloc() until after the parameters pass validation.

Also in calculateFibonacciSequence(), you wrote return 0, but you are actually returning a null pointer, not a number 0. It would be clearer to write return NULL.

As a nitpick, I think two spaces for indentation is too stingy for readability. Small indentation also encourages excessive nesting, which is poor programming practice. Try four spaces instead.

Overall, though, not bad!