Return to Answer

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t2, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typos in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.

While this question already has many answers, one of which is accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t2, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typos in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t1, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typo in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t2, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typos in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t1, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typo in code.

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t1, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

EDIT: Fixed typo in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.