Python Recursive Function


RECURSIVE FUNCTION


A function can call other functions. It is even possible for the function to call itself. These type of construct are termed as recursive functions.

 Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.

 # An example of a recursive function to
# find the factorial of a number

 def calc_factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

     if x == 1:
        return 1
    else:
        return (x * calc_factorial(x-1))

 num = 4

print("The factorial of", num, "is", calc_factorial(num)

EXPLANATION

In the above example, calc_factorial() is a recursive functions as it calls itself.
When we call this function with a positive integer, it will recursively call itself by decreasing the number.
Each function call multiples the number with the factorial of number 1 until the number is equal to one. This recursive call can be explained in the following steps.

  1. calc_factorial(4) # 1st call with 4
  2. 4 * calc_factorial(3) # 2nd call with 3
  3. 4 * 3 * calc_factorial(2) # 3rd call with 2
  4. 4 * 3 * 2 * calc_factorial(1) # 4th call with 1
  5. 4 * 3 * 2 * 1 # return from 4th call as number=1
  6. 4 * 3 * 2 # return from 3rd call
  7. 4 * 6 # return from 2nd call
  8. 24 # return from 1st call
Our recursion ends when the number reduces to 1. This is called the base condition.

RECURSION FUNCTION TO PRINT A STRING BACKWARDS

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.
# Function to print reverse of the passed string 
def reverse(string):
    if len(string) == 0:
        return string
    else:
        return reverse(string[1:]) + string[0]
a = str(input("Enter the string to be reversed: "))
print(reverse(a))

RECURSION FUNCTION IN CALCULATON OF POWER a power b

def power(base,exp):
    if(exp==1):
        return(base)
    if(exp!=1):
        return(base*power(base,exp-1))
base=int(input("Enter base: "))
exp=int(input("Enter exponential value: "))
print("Result:",power(base,exp))

RECURSION FUNCTION TO PRINT FIBONACCI SERIES

def recur_fibo(n):
   """Recursive function to
   print Fibonacci sequence"""
   if n <= 1:
       return n
   else:
       return(recur_fibo(n-1) + recur_fibo(n-2))
if nterms <= 0:
   print("Plese enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(recur_fibo(i))

BINARY SEARCH

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

PROGRAM -

def binarySearch (arr, l, r, x):
  
    # Check base case
    if r >= l:
  
        mid = l + (r - l)/2
  
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
          
        # If element is smaller than mid, then it 
        # can only be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
  
        # Else the element can only be present 
        # in right subarray
else:
            return binarySearch(arr, mid + 1, r, x)
  
    else:
        # Element is not present in the array
        return -1
  
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
  
if result != -1:
    print "Element is present at index % d" % result
else:
    print "Element is not present in array"

PRE-REQUISITS OF BINARY SEARCH

  1. The giver array or sequence must be sorted.
  2. its sort-order and size must be known.

Recursive function to implement binary search algorithm

def binary_search(alist, start, end, key):   
    """Search key in alist[start... end - 1]."""
    if not start < end:
        return -1
 
    mid = (start + end)//2
    if alist[mid] < key:
        return binary_search(alist, mid + 1, end, key)
    elif alist[mid] > key:
        return binary_search(alist, start, mid, key)
    else:
        return mid
 
 
alist = input('Enter the sorted list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))
 
index = binary_search(alist, 0, len(alist), key)
if index < 0:
    print('{} was not found.'.format(key))
else:
    print('{} was found at index {}.'.format(key, index))


Recursion Vs Iteration

Iteration is when a loop repeatedly executes until the controlling condition becomes false.
Iteration 
def iterative_sum(n):
    result = 1
    for i in range(2,n+1):
        result *= i
    return result
print(iterative_sum(5))

Recursion

Recursive function is when a function calls itself
def recursive_sum(n):
    if n == 1:
        return 1
    else:
        return n * recursive_sum(n-1)
print(recursive_sum(5))

Computing GCD recursively

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
GCD=gcd(a,b)
print("GCD is: ")
print(GCD)

Advantages of Recursion

  1. Recursive functions make the code look clean and elegant.
  2. A complex task can be broken down into simpler sub-problems using recursion.
  3. Sequence generation is easier with recursion than using some nested iteration.

Disadvantages of Recursion

  1. Sometimes the logic behind recursion is hard to follow through.
  2. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
  3. Recursive functions are hard to debug.

Comments

Post a Comment