Recursion in Python

Board Infinity -

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

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 valid
if n <= 0:
    print("Input must be greater than 0.")
else:
    print("Fibonacci series:")

for i in range(n):
 print(fib(i))

Output

10
Fibonacci series:
0
1
1
2
3
5
8
13
21
34

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

7
5040

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

10
3628800

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

6
720

write your code here: Coding Playground