# Using tail recursion and Fibonnaci-style recursion to solve the Fibonnaci sequence

suggest changeThe simple and most obvious way to use recursion to get the Nth term of the Fibonnaci sequence is this

int get_term_fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return get_term_fib(n - 1) + get_term_fib(n - 2); }

However, this algorithm does not scale for higher terms: for bigger and bigger `n`

, the number of function calls that you need to make grows exponentially. This can be replaced with a simple tail recursion.

int get_term_fib(int n, int prev = 0, int curr = 1) { if (n == 0) return prev; if (n == 1) return curr; return get_term_fib(n - 1, curr, prev + curr); }

Each call to the function now immediately calculates the next term in the Fibonnaci sequence, so the number of function calls scales linearly with `n`

.

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents