Published: Sat 05 September 2020
By Sri
In Python .
Here are 5 simple Python recursive functions that will get you started with the practicing recursion.
These are exercise problems taken from the book - Data Structures and Algorithms in Python Michael H. Goldwasser, Michael T. Goodrich, and Roberto Tamassia
Write a short recursive Python function that finds the minimum and maximum values in a sequence without using any loops.
The idea here is to split the list of numbers into two halves and recursively call the function on each of them and making a comparison until you have a list containing only one number in which case you just return the number.
# Recursive algorithm for finding maximum number in
# a array.
def maximum_in_list ( nums ):
l = len ( nums )
if l == 1 :
return nums [ 0 ]
m1 = maximum_in_list ( nums [ 0 : l // 2 ])
m2 = maximum_in_list ( nums [ l // 2 : l ])
if m1 > m2 :
return m1
else :
return m2
Describe a recursive algorithm to compute the integer part of the base-two logarithm of n using only addition and integer division.
The idea here is to recursively call the function while dividing the number by 2. Returning 0 if the number is less than 2 or return 1 if the number is equal to 2.
# Recursive algorithm to compute
# integer part of base 2 logarithm of n.
def log_base2 ( n ):
if n < 2 :
return 0
if n == 2 :
return 1
return 1 + log_base2 ( n // 2 )
Write a short recursive Python function that takes a character string and outputs its reverse.
This is a little hard to explain for me. The idea here is to get to the last character of the string by recursively calling the function where the 2 inputs are the first character of the string and the rest of the string. Once we get to the last character, we concatenate the inputs and return the result.
# Recursive function to reverse a string.
def reverse_string ( string ):
def get_reversed_string ( string_a , string_b ):
## check if string_b
## is the last letter of the string.
if len ( string_b ) == 1 :
return string_b + string_a
else :
return get_reversed_string ( string_b [ 0 ], string_b [ 1 :]) + string_a
return get_reversed_string ( string [ 0 ], string [ 1 :])
Write a short recursive Python function that determines if a string is a palindrome
The idea is pretty straightforward once you figured out how to reverse a string.
# Recursive function to check
# if a string is a palindrome
def is_palindrome ( string ):
if string == reverse_string ( string ):
return True
return False
Use recursion to write a Python function for determining if a string s has more vowels than consonants.
The idea here is to split the string into two halves just like I did finding the maximum number in a list, in the very first program above. Once the string has only one character I will check whether it is a vowel or not, and thus the results get added up recursively.
# Python function for determining if a
# string has
# more vowels than consonants.
def if_more_vowels ( string ):
def count_vowels ( string ):
l = len ( string )
if l == 1 :
if string . lower () in [ 'a' , 'e' , 'i' , 'o' , 'u' ]:
return 1
return 0
vowels_a = count_vowels ( string [ 0 : l // 2 ])
vowels_b = count_vowels ( string [ l // 2 : l ])
return vowels_a + vowels_b
vowels = count_vowels ( string )
if vowels > len ( string ) - vowels :
return True
return False
Thanks for reading, let me know your thoughts or share your favorite recursive programs.
Happy learning.