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 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)
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, string_b[1:]) + string_a return get_reversed_string(string, string[1:])
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.