# 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.

• 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.

• 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

 def f1():  ##  <---           ##     |           ##     | (recursive call)           ##     |  Calling the function itself    f1()   ##  ----

## 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

 def fib(n):    if n <= 1:     return n    else:     return(fib(n-1) + fib(n-2))n = int(input())# verifying if n is validif n <= 0:    print("Input must be greater than 0.")else:    print("Fibonacci series:")for i in range(n): print(fib(i))

Output

 10Fibonacci series:0112358132134
write your code here: Coding Playground

### Example 2: factorial of a number

The factorial of 6 is denoted as 6! = 12345*6 = 720.

Code

 def fact(n):     # Recursive function    if n == 1:        return n    else:        return n * fact(n-1)i = int(input())if i < 0:    print('Error')elif i == 0:    print("Factorial of number 0 is 1")else:    print(fact(i))

Output

 75040
write your code here: Coding Playground

## 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)

 def r_fac(n): if (n == 0): return 1 return n * r_fac(n-1)print(r_fac(int(input())))

Output

 103628800
write your code here: Coding Playground

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)

 def r_fac(n, x = 1): if (n == 0): return x return r_fac(n - 1, n * x)print(r_fac(int(input())))

Output

 6720
write your code here: Coding Playground