Python for Data Science

Recursion in Python

Board Infinity
Board Infinity
Recursion in Python

    Python Libraries

    Most important Python Libraries for Data Science

    Arrays In Python

    List vs Tuple: Differences

    List vs Set: Key Differences

    Python List append() Method

    Dictionary of Lists

    Sort Dictionary in Python

    String Comparision in Python

    Zip Function in Python

    Iterators in Python

    Recursion in Python

    with statement in Python

    Python Docstring

    JSON file in Python: Read and Write

    Dictionary to JSON: Conversion in Python

    Beginner's Guide to NumPy in Python

    Numpy in Python

    How to perform Matrix Multiplication with Numpy Python

    What is pandas in python - Pandas Introduction

    Count Rows and Column with Pandas

    How to create an Empty Dataframe in Python using Pandas?

    Pandas append() in Python

    GroupBy Python Function & How To Use It!

    Master Data Visualization using Python

    Python Socket Programming

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