5 Simple Recursion Programs 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.