# 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