# Generating the Fibonacci Sequence with Recursion

Solving a common question in Programming Interviews.

## Software Interviews

A while ago, I had an interview for a **Software Developer** position.

After some general questions, they got me into some **thinking**. Knowing some programming languages is excellent, but can you apply them to real use cases?

They asked me if I could use recursion to get any **nth number from the Fibonacci Sequence**. Let's see how we can approach this problem.

## What is the Fibonacci sequence

Also known as the Fibonacci numbers, it's a sequence of integers starting from 0 (or 1) and going on indefinitely.

The main property of this sequence is that **each number is the sum of the two preceding ones.**

For instance, the first 10 values are `0 1 1 2 3 5 8 13 21 34`

.

## What about Recursion?

Recursion is an interesting topic in mathematics and, consequently, programming.

It consists of dividing a problem into smaller and similar bits, solving the main problem though many iterations.

To do so, **we have to call a function from within the function itself**.

Note that, in some cases, this can lead to an infinite loop.

## Solving the problem

To solve this problem, we can virtually use any programming language. In this case, I'm using **C#**.

The final function should look similar to this:

```
int GetNthFibonacci(int n)
{
if (n == 0) return 0;
if (n < 2) return 1;
return NthFibonacci(n-1) + NthFibonacci(n-2);
}
```

Let's analyze it.

Firstly, we're returning an integer and accepting an integer, which will be the **nth number** of the sequence.

`int GetNthFibonacci(int n)`

Secondly, we need to make sure that the **first 3 numbers** always correspond to `0 1 1`

.

```
if (n == 0) return 0;
if (n < 2) return 1;
```

Finally, we get to the actual **recursion**. The next number in order will be the sum of the two preceding ones.

`return NthFibonacci(n-1) + NthFibonacci(n-2);`

### Using the function

We can now generate the sequence. For example, let's get the first 10 numbers in console.

```
for (int i = 0; i < 10; i++)
{
Console.Write(NthFibonacci(i) + " ");
}
```