# 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 <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;
}

if (start != 0 && start != 1) {
return 0;
}

// Get the seed values
if (start == 0) {
numbers = 0;
numbers = 1;
} else {
numbers = 1;
numbers = 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);

// Did they specify a start value
if (argc > 2) {
start = atoi(argv);
}

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

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

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

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

// Free memory
free(sequence);

return 0;
}

• Since you're just printing the numbers, what is your original task: to print them or to compute them in an array? – Vedran Šego Jan 14 '14 at 0:26
• @syb0rg I accepted your answer just now. Originally I was giving people time to post/edit and then I forgot to accept an answer. While your recursive example doesn't really do what I want, your post is very informative. Thanks! – Brandon Wamboldt Jan 28 '14 at 0:28
• @BrandonWamboldt Thanks! I did add a faster iterative solution in case you did not want recursion. – syb0rg Jan 28 '14 at 0:30

## What you did well on:

• 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;
}
}

• Isn't declaring the loop counter inside the loop statement a syntax error in C? Or does the OP have C99? – Jamal Jan 12 '14 at 0:26
• @Jamal It was an error, so I kept that part how it was – Brandon Wamboldt Jan 12 '14 at 0:33
• @Jamal Yes, in older standards. But C99 is the "lowest" standard that should be used (in my opinion). – syb0rg Jan 12 '14 at 0:37
• Okay. For the short time I've written C (mostly in just one class), I was always used to declaring it outside since C99 wasn't in use. – Jamal Jan 12 '14 at 0:40
• I'd consider the global array, with a fixed size limit, and recursion not an improvement, but rather three steps back. – 200_success Jan 18 '14 at 11:44

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.

• Hmm, I may have re-iterated some points you had. My answer was in the works when you posted this and didn't notice. – syb0rg Jan 12 '14 at 0:18
• No problem - if we both thought the same things, there's perhaps more chance of them being true :-) BTW your recursive solution is notationally neat but horribly inefficient. Do a Fibonacci of 46 and it calls fibonacci 9615053904 times (and takes correspondingly long). – William Morris Jan 12 '14 at 2:44
• Yeah, I think I had a Schlemiel the Painter's algorithm. I have edited in a solution that uses memoization now, which is much faster. – syb0rg Jan 12 '14 at 4:11

You allocate memory using malloc(), based on a user-submitted number that is never checked. If the user supplies -1 in argv, 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.

• Makes sense, thanks. Never had to do memory management manually before. – Brandon Wamboldt Jan 14 '14 at 2:15

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.