Week 7 - Recursion (Slightly late again)

The topic of this week is recursion. To sum it up simply, recursion is the process of calling a function within itself, although it can more accurately be described as repeatedly performing the same action on a certain object. In computer science recursion and loops are generally seen as two ways of doing the same job in most cases. Unlike with loops however (unless somebody uses "while True"), one must be careful with recursion to make sure there is a stop condition in the function. If one doesn't, they run the risk of running out of memory space, which, suffice to say, may cause issues. For some situations, such as when, one is going over a nested list of unknown depth, recursively going over the list is far simpler and more efficient than using loops.

To recursion, if I need to find out the minimum number of moves needed to complete a Tower of Hanoi game with x number of blocks and 4 pegs,

def best_split(n: int) -> int:
    """Determine the optimal value to split at."""
    choices = [i for i in range(1, n)]
    num_moves = []
    if n == 1:
        return (1,1)
    else:
        num_moves = [(2 * best_split(n - i)[0] + 2 ** i - 1) for i in choices]
        optimal_i = choices[num_moves.index(min(num_moves))]
        return (min(num_moves), optimal_i)

Note that this function also returns the best value to split the tower at, but that is largely irrelevant to the current discussion. As can be seen, I call the function within itself at line 8. I also have an appropriate stop condition where the function will stop running at line 5. Both are necessary for a recursive function.

Recursion has, at this point, permeated so much into my life that I think about iterative problems recursively.