Programming

Finding Fibonacci numbers in C is easy, even when using recursion. Here is a program that can find the 1,000,000th Fibonacci number. It's too big to paste the output of the program here but here you can find it on pastebin here.

#include <stdio.h>
#include <gmp.h>

void fib(int idx, mpz_t *a, mpz_t *b, mpz_t *c)
{
	mpz_add(*c, *a, *b);
	mpz_set(*a, *b);
	mpz_set(*b, *c);
	if (idx < 0) return;
	fib(idx - 1, a, b, c);
}

int main()
{
	mpz_t a; mpz_init(a);
	mpz_t b; mpz_init(b);
	mpz_t c; mpz_init(c);
	mpz_set_str(a, "1", 10);
	mpz_set_str(b, "0", 10);

	fib(1000000, &a, &b, &c);
	mpz_out_str(stdout, 10, c);
	printf("\n");
	
	mpz_clear(a);
	mpz_clear(b);
	mpz_clear(c);
	return 0;
}

You need to compile with the -O2 flag in GCC. If your recursive call is at the end of the function, this is called tail recursion, and when using that flag, the GCC compiler is smart enough to not allocate more memory on the stack every time it does a recursive call, so you don't run out of memory.