January 19, 2019
HomeAlgorithms and Data StructuresPython recursive function examples

Python recursive function examples

By  Algorithms and Data Structures, Code Snippets, Interview Questions  0 Comments

Table of contents

Recursive exponential

Given two exponential numbers with the same base, the multiplication is another exponential number with the same base but we add the exponents. We can utilize this observation and define a recursive exponential formula. If (n) is even number, return the square of x^(n/2) because

1
x^n = x^(n/2) * x^(n/2)

otherwise, return (x) multiplied by x^(n-1) because

1
x^n = x * x^(n-1)

and the base case when (n) is either 0 or 1

1
2
If (n) is zero return 1
If (n) is one return (x)

Implementation

Here is the implementation in Python…

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def RecursiveExp(x, n):
    # First base case
    if n == 0:
        return 1
    
    # Second base case
    if n == 1:
        return x
 
    # Even values of (n)
    if n % 2 == 0:
        y = RecursiveExp(x, n / 2)
        return y * y
    # Odd values of (n)
    else:
        y = RecursiveExp(x, n - 1)
        return x * y
 
# Examples
for i in range(10):
    print "2 to the power of {} = {}".format(i, RecursiveExp(2, i))

If you run the code above you should get the output below…

Python
1
2
3
4
5
6
7
8
9
10
2 to the power of 0 = 1
2 to the power of 1 = 2
2 to the power of 2 = 4
2 to the power of 3 = 8
2 to the power of 4 = 16
2 to the power of 5 = 32
2 to the power of 6 = 64
2 to the power of 7 = 128
2 to the power of 8 = 256
2 to the power of 9 = 512

Recursive max

Write a recursive function to find the maximum value element in an Array of size N.

Algorithm

One way to do that is to split the array into two halves then find the largest number in each portion then return the largest of the two. Please note that as we divide the array into halves we are actually copying data instead of operating in place.

Implementation

The following is a suggested solution in Python…

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Recursive function to compute max
def recursiveMax(A):
 
   # If empty do nothing
   if len(A) == 0:
      return
 
   # Base case
   if len(A) == 1:
      return A[0]
 
   # Find max in left and right portions
   lMax = recursiveMax(A[:len(A)/2])
   rMax = recursiveMax(A[len(A)/2:])
 
   # Return the greater one
   if lMax >= rMax:
      return lMax
   else:
      return rMax
 
# Array with even size
A = [7, 1, 9, 0, 8, 2, 5, 3, 4, 6]
# Array with odd size
B = [7, 1, 9, 0, 8, 2, 5, 3, 4, 6, 10]
# Array wih only 2 elements
C = [4, 6]
# Array with only 1 element
D = [7]
# Empty array
E = []
 
# Call the function
print "Max of A = {}".format(recursiveMax(A))
print "Max of B = {}".format(recursiveMax(B))
print "Max of C = {}".format(recursiveMax(C))
print "Max of D = {}".format(recursiveMax(D))
print "Max of E = {}".format(recursiveMax(E))

If you run the code above, you should get the output below…

Python
1
2
3
4
5
Max of A = 9
Max of B = 10
Max of C = 6
Max of D = 7
Max of E = None

Recursive multiplication

Write a Python recursive function to compute the product of two positive integers.

Algorithm

The product of two positive integers (A*B) is nothing but the sum of the first integer (A), (B) times

Implementation

Here is the code in Python…

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Includes
def RecursiveProduct(a, b):
 
# Base case 1
if a == 0 or b == 0:
return 0
# Base case 2
if b == 1:
return a
return a + RecursiveProduct(a, b-1)
 
print "3 x 4 = {}".format(RecursiveProduct(3, 4))

If you think about the code above, it is not recursive naturally but iterative. What we are doing actually is performing iteration using recursion which is a weird way to do it.

Recursive sum

Write a recursive function to find the sum of all elements in an Array.

Algorithm

If the array is only one element then return that element otherwise return the first element added to all elements that come after.

Implementation

The following is a suggested solution in Python…

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Recursive function to compute sum
def recursiveSum(A):
 
   # If empty do nothing
   if len(A) == 0:
      return
 
   # Base case
   if len(A) == 1:
      return A[0]
 
   # Return 1st element added to the
   # sum of the rest of the array
   return A[0] + recursiveSum(A[1:])
 
# Input array
A = [7, 1, 9, 0, 8, 2, 5, 3, 4, 6]
 
# Call the function
print "Sum of A = {}".format(recursiveSum(A))

If you run the code above, you should get the output below…

Python
1
Sum of A = 45

Recursive average

We are going to calculate the average in a similar way to sum. Note that…

1
Avg(A) = (A[0] + … + A[n-1])/n = A[0]/n + … + A[n-1]/n

The only difference is that we divide by (n). Here is an implementation in Python…

Implementation

Python
1
2
3
4
5
6
7
8
9
10
def RecursiveAvg(A, i, n):
 
# Base case
if i == n-1:
return A[i]/n
 
return A[i]/n + RecursiveAvg(A, i + 1, n)
 
A = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]
print "Average of A = {}".format(RecursiveAvg(A, 0, 10))

If you run the code snippet above you should get

Python
1
Average of A = 5.5

Recursive uppercase

Write a recursive function to convert a string to uppercase

Algorithm

As we indicated earlier, this is also not recursive naturally but iterative. What we are doing actually is performing iteration using recursion

Implementation

Here is an example Python implementation…

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Parameters: input string,
# character index, string size
def RecursiveUpper(x, i, n):
   # Convert character to CAPS
   # only if it is a small letter
   if x[i] >= ord('a') and x[i] <= ord('z'):
  
      # To convert a character into capital
      # letter case add to its ASCII value
      # the difference between A and a
      x[i] = x[i] + (ord('A')-ord('a'))
 
   # Stop when i = n-1
   if i == (n-1):
      return x
 
   # Advance index (i) then call again
   return RecursiveUpper(x, i + 1, n)
 
# Example string. We used a byte array
# so that we can modify it as by array
# is mutable
x = bytearray(b"redfOx")
# Call the function
x = RecursiveUpper(x, 0, len(x))
# In order to print a byte array we
# need to convert it back to ascii
print(x.decode("ascii") )

Thanks for visiting. For questions and feedback please use the comments section below.

More from my site

Tags:, , ,

About Author

Mohammed Abualrob

Software Engineer @ Cisco

Add a Comment

Your email address will not be published. Required fields are marked *