# Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive methodology, certain problems can be solved quite easily.

**A Mathematical Interpretation**

Let us consider a problem that a programmer have to determine the sum of first n natural numbers, there are several ways of doing that but the simplest approach is simply add the numbers starting from 1 to n. So the function simply looks like, (The markdown render of Github does not support LaTeX, better to read it in [Typora](https://typora.io))

> $f(n) = \sum\_{i=1}^n i $ or `f(n) = 1 + 2 + ... + n`

but there is another mathematical approach of representing this,

> $f(n) = 1\qquad(n = 1)$ or `f(n) = 1 when n == 1`
>
> $f(n) = n + f(n-1)\qquad(n>1)$ or `f(n) = n + f(n - 1) when n > 1`

**Can recursion make code more readable?**

Umm, when you understand recursion, it could.

> Talk is cheap, show me the code. [ref.](https://www.goodreads.com/quotes/437173-talk-is-cheap-show-me-the-code)

Here is an example for calculating [Fibonacci](https://en.wikipedia.org/wiki/Fibonacci_number).

```python
# Recursion
def fibonacci(n):
    if n <= 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
```

An experienced programmer should have no problem understanding the logic behind the code. As we can see, in order to compute a Fibonacci number, **Fn**, the function needs to call **Fn**-1 and **Fn**-2. **Fn**-1 recursively calls **Fn**-2 and **Fn**-3, and **Fn**-2 calls **Fn**-3 and **Fn**-4. In a nutshell, each call recursively computes two values needed to get the result until control hits the base case, which happens when **n<=2**.

You can write a simple **main()** that accepts an integer **n** as input and outputs the **n**’th Fibonacci by calling this recursive function and see for yourself how slowly it computes as **n** gets bigger. It gets horrendously slow once **n** gets past 40 on my machine.

Here is a non-recursive version that calculates the Fibonacci number:

```python
# Non-Recursion
def fibonacci(int n):
	if n <= 2:
		return 1
	last = 1
	nextToLast = 1
	result = 1
	for i in range(3, n+1):
		result = last + nextToLast
		nextToLast = last
		last = result
	return result
```

The logic here is to keep the values already computed in variables **last** and **nextToLast** in every iteration of the **for** loop so that every Fibonacci number is computed exactly once. In this case, every single value is computed only once no matter how big **n** is.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://algo.aspires.cc/fundamental/ch1-recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.