Recursion in Python

Recursion is a method whereby a function calls itself for some reason.

Recursion is best used when operating on a static data set. If the data is copied to a sub-call, beware because a sufficiently large data set could over-run memory.

import random

guess_number = random.randint(1,1000)

def main():
    # Recursive Addition
    print(recadd(11,11))
    print(recadd_alternate(11,11))

    
    # Recursive Multiplication
    n = recmul(12,12)
    print(n)

    # Recursive sum of natural numbers
    n = recsum(5)
    print(n)

    # Recursive Factorial (*standard example)
    f = factorial(5)
    print(f)

    # Recursive Fibonacci (*relatively common example)
    f = []
    for i in range(1, 10):
        f.append(fibonacci(i))

    print(f)

    # Recursive Bubble Sort
    list = [5, 1, 4, 2, 3]
    list = recsort(list)
    print(list)

    # Guessing numbers using
    # recursive binary search:
    print(guess(0,1000), '=', guess_number)


# Add one for every A (count A,)
# then add B to it.
def recadd(a, b):
    if a > 0:
        return 1 + recadd(a-1, b)
    else:
        return b # Base case: add B to result.

def recadd_alternate(a,b):
    if a > 0:
        return 1 + recadd(a-1, b)
    elif b > 0:
        return 1 + recadd(a, b -1)
    else:
        return 0


# Recursive Multiplication
def recmul(a,b):
    if b > 0:
        return a + recmul(a, b - 1)
    else:
        return 0

# The sum of the first n numbers
def recsum (n):
    if n > 0:
        return n + recsum(n-1)
    else:
        return 0

# Recursive Factorial
def factorial(n):
    if n > 1:
        return n * factorial(n-1)
    else:
        return 1
    
# Recursive fibonacci
def fibonacci(n):
    if n > 1:
        return fibonacci(n - 1) + fibonacci(n - 2)
    else:
        return n

def recsort(list):
    for i in range(len(list)-1):
        if list[i] > list[i+1]:
            (list[i], list[i+1]) = (list[i+1], list[i])
            return recsort(list)
        else:
            i = i + 1

    # no re-sort triggered == list is sorted.
    return list

def guess(a, b):
    print(a,b)
    my_guess = random.randint(a, b)
    if my_guess < guess_number:
        return guess(my_guess+1, b)
    elif my_guess > guess_number:
        return guess(a, my_guess-1)
    else:
        return my_guess


if __name__ == '__main__':
    main()

This counts A using recursion, then adds B to the result. The alternate version also counts B, for illustrative purposes.

This is like a for loop that adds a to itself b number of times.

This function is easy to understand. Add the number, plus the number next to it, and “repeat. The two components are A and B where A is the number, and B is the next number “and all numbers after it,” since the function calls itself. Thus it is equivalent to removing the brackets;

• (5 + (4 + (3 + (2 + (1 + 0)))))

What happens in a recursive function like this is that the code drills down to the case 1+0 and evaluates it – like the brackets – and then evaluates 2 + n where n is the evaluated 1+0. Then, this answer (3) is given to “3 + n” and so on until we reach 5 + (the evaluated remainder) which is 10, and we get 15. So the 5 is added last and the 1 and 0 are added first, in terms of linear time. The value then “percolates up” through the recursive memory calls until the final value is returned as 15, to the original caller of the function.

The idea here is exactly the same as in recursive sum.

Here the idea is essentially similar. We take one step and repeat until finished. This is the hallmark of a recursive algorithm, the ability to take one step and then point towards the next step.

Another classic recursive algorithm with educational value is the Binary Search algorithm. A great way to understand it is with a number guessing game algorithm.

• The function guess takes two parameters, a and b, representing the current search range.
• It generates a random guess (my_guess) within the range [a, b].
• If the guess is less than the target number (guess_number), the function recursively calls itself with an updated search range [my_guess + 1, b].
• If the guess is greater than the target number, it recursively calls itself with an updated search range [a, my_guess - 1].
• If the guess is equal to the target number, it returns the correct guess.

This guessing game effectively narrows down the search range in a manner similar to a binary search, making it a fun and interactive way to understand the concept.

This sorting algorithm is a recursive implementation of the Bubble Sort algorithm. In each pass through the list, adjacent elements are compared, and if they are in the wrong order, they are swapped. This process is repeated until the entire list is sorted.

The base case for the recursion is when no swaps are needed during a pass, indicating that the list is already sorted. In this implementation, the base case is reached when the loop completes without triggering any re-sorting.

Here's a brief breakdown of the steps in the code:

1. Iterate through the list. 2. If an element is greater than its adjacent element, swap them. 3. Recursively call the `recsort` function on the modified list. 4. If no swaps are triggered during a pass, return the sorted list.

While Bubble Sort is not the most efficient sorting algorithm, it is a good educational example and helps in understanding the concept of sorting through repeated comparisons and swaps.