# Recursion in Python

## Introduction

Recursion is a process in which something is defined in terms of itself. In easy words, it is a process in which a function makes a call to itself.

## Advantages of using recursion

- Recursion can be utilized by dividing complex functions into smaller sub-problems.
- Through recursion, sequence generation can be easily achieved when compared to nested iteration.
- Recursive functions are easy to look at and are more efficient.

## Disadvantages of using recursion

- A lot more time and memory are used while doing recursion making it difficult to use.
- The recursive function also is hard to debug.
- The logic behind the recursion can be tough sometimes to think about and also hard to implement.

## Syntax

## Examples

### Example 1: Printing a Fibonacci sequence through recursion

A sequence in which each element is the sum of two numbers preceding the current element such type of sequence is called a Fibonacci sequence.

**Code**

**Output**

### Example 2: factorial of a number

The factorial of 6 is denoted as 6! = 1*2*3*4*5*6 = 720.

**Code**

**Output**

## Tail-Recursion

Tail recursion is a special type of recursion in which the last procedure of a function makes a recursive call. The recursion can be self-operating as it may perform the request in the current stack and rather than generating a new stack frame it returns the output. The tail recursion is better than the non-tail recursion as the compiler makes it more optimized.

**Now if it is possible to make a program more optimised by using tail recursion despite non-tail recursion?**

Now let us see the code below, to calculate the factorial, at first, the code may look like tail recursive but it is not. It is a non-tail recursive code. If we take a good look, the return value of r_fac(n-1) is used in the r_fac(n) function, So the last thing done by the r_fac(n) function is not making the call to r_fac(n-1).

**Code (non-tail recursive function)**

**Output**

We can also make the above function a tail recursive function. We just need to add one more argument and the second argument is the value of factorial. When n becomes zero, we will return the factorial f the number desired.

**Code (tail recursive function)**

**Output**