Recursion in Python Explained with example

# houses = ["Eric's house", "Kenny's house",
#           "Kyle's house", "Stan's house", "Pallavi's house", "James's house"]


houses=[67, 76, -35, 87, 87]

def deliver_presents_recursively(houses):
    if (len(houses) > 1):
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]
        deliver_presents_recursively(first_half)
        deliver_presents_recursively(second_half)

        i = j = k = 0

    #    store the smaller element in the k position of array
        while i < len(first_half) and j < len(second_half):
            if first_half[i] < second_half[j]:
                houses[k] = first_half[i]
                i += 1
            else:
                houses[k] = second_half[j]
                j += 1
            k += 1

        # When we run out of elements in either L or M,
        # pick up the remaining elements and put in arr[k]
        while i < len(first_half):
            houses[k] = first_half[i]
            i += 1
            k += 1

        while j < len(second_half):
            houses[k] = second_half[j]
            j += 1
            k += 1

def deliver_presents_recursively2(houses):
    if (len(houses) > 1):
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]
        deliver_presents_recursively2(first_half)
        deliver_presents_recursively2(second_half)

        i = j = k = 0

    #   store the smaller element in the k position of array
        while i < len(first_half) and j < len(second_half):
            if first_half[i] > second_half[j]:
                houses[k] = first_half[i]
                i += 1
            else:
                houses[k] = second_half[j]
                j += 1
            k += 1

        # When we run out of elements in either L or M,
        # pick up the remaining elements and put in arr[k]
        while i < len(first_half):
            houses[k] = first_half[i]
            i += 1
            k += 1

        while j < len(second_half):
            houses[k] = second_half[j]
            j += 1
            k += 1


deliver_presents_recursively(houses)
# print(houses)
array1 = [" "] * len(houses)
array2 = [" "] * len(houses)
m = len(houses)//2
arr1 = houses[m:]
arr2 = houses[:m]

kk = 0
while(kk < len(arr1)):
    deliver_presents_recursively2(arr1)
    deliver_presents_recursively(arr2)
    kk += 1
print(arr1,arr2)

Seems like a long algorithm right? I am doing multiple things together.

There are two functions one for decreasing order of sorting and the next is the increasing order of sorting.

I will explain the theory first.

Recursion means when a function calls itself again and again once a condition is met. It is equivalent to iteration as well.

The same thing is happening here. I have this list which could be a list of integers or strings. I want to call the deliver_presents_recursively function over each element of the function to get a sorted list. This is merge sort.

Before you go for a recursive function, you should think of a few base conditions to escape maximum function calls.

Here the base condition is until the length of houses is greater than one, which is always true. But this is not an infinite loop. This is a nontailed recursion, which is different when the execution is concerned.

We are doing a few operations after the recursion calls as well like comparing the ith and jth element of the first half and second half array and storing them in the kth position of the houses array. Lastly storing the residual element in kth position of the houses list.

The best way to analyze this program for Recursion In python

You can see here what variables I am tracking to investigate the program. This will help you know when loops are executed and under what conditions they come out of the loop. This helps in optimizations.

If you see the second third fourth block inside the function, you will notice that under suitable conditions, if the ith element is executed in the 2nd block then the 3rd block is executed, which means you put the ith element in the kth position of the houses and for that iteration put all the rest element from the second half in the kth positions of houses which gives a new version of the list.

This iteration is for the first recursive call for the first half, after that is done, control will revert to the second recursive function with the second half, and the same process happens.

The last piece of the puzzle is how many times the recursive call occurs, here comes the other base operation which is block 2, 3, and 4 together. These blocks would get executed until k = length of houses, and then the cursor escapes, no more recursive calls.

Hope It helped…