Week 7 Recursion

Recursion is a programming technique useful for its brevity. It can replace long and error-prone iterative versions of the same solution. And its implementation can be shorter and easier to read using condensed logic statements. Practically, it involves a function calling itself repeatedly, until directed to a block that ends the calls given some condition. In this class, we use recursion most often to deal with nested ADTs like trees and linked lists, or, more basically, nested Python lists. If you were given the task of filtering out elements in a 1D list with some condition, an iterative method of checking every single element is very intuitive. This approach runs into problems, however, when you have an n-D nested list. It may steer you towards thinking you need n-nested for loops...but you don't know what n is. This is a classic example of recursion giving an elegant solution to the problem. You set up the function such that there is a block that processes the list as if it were a 1D list. This is called the base case, and it is here that we stop the repeated calls to itself. We know how to solve the 1D list problem. The above iterative method would work (or if you're a purist, you can generalize the recursion to single elements). Once we have a solution, we return it to the general case block, where it can be think of as the block that puts all the base cases together. In the filtering problem, if I reach the base case, I return a list of wanted elements back to the general case, and a portion of the general case block could be joining all the lists returned by the base cases to give a list of every single wanted elements in the n-D nested list. Given a nested problem in the form of [ [Problem], [Problem, [Problem] ] ], recursion solves it by reducing it to a single Problem, giving a Solution, then constructing the solution [ [Solution], [Solution, [Solution] ] ] -> [Solution, Solution, Solution] to be returned. This is the logic behind the method of recursion problem solving.