Recursion

# Example of recursion in nature and physical systems (i.e. formation of frost crystals)

What is Recursion?
Recursion as a concept has been around in history before the invention of computers. Properties of recursion can easily be observed in nature as well as in physical systems. At this point in the course, I’m pretty confident that most, if not all, students in CSC148 are familiar with the concept of recursion. Everybody understands recursion a little bit differently, but the fundamentals are typically the same; when you create a recursive function, you start by defining you base cases that solves the problem when it’s “small”, then implement a solution that essentially breaks your problem into smaller chunks up until your base case is reached. Recursion as a programming method of solving problems has HUGE appeal in terms of functionality, and I would think that it is one of the fundamental concepts of computer programming.

# Recursion used in advertising of products

Recursion in application:
To illustrate how recursion is used in application, take for example the following function:

def count(lst):
    return sum([1 + count(x) if isinstance(x, list) else 1 for x in lst])

This function counts the number of elements in a list, including elements within nested lists. It does so by counting the number of non-list elements in lst, and calls itself on lists that are nested within lst. The base case in this example would be the else statement that tells the function to just return 1 if x is not a list, or in other words, a non-list element. A typical function that solves the same problem, without using recursion, could span from 8-25 lines, depending on how one implements the function. However, with the use of a combination of recursion and list comprehension, all that code is squeezed into a single line. Thus the use of recursion in this particular problem presents a cleaner, more concise view of how count() is implemented. As well, the use of recursion simplifies how the programmer approaches this particular problem, which can be taken to be true for any other problem that is of a recursive nature.

Be aware...
The use of recursion can be tricky at times; the possibility for infinite regress is always open if the base case is not defined clearly, such that recursion DOES not ever reach a base case, and instead loops in a continuous manner indefinitely. However, with a strong understanding of how recursion works (complemented with a little practice), the use of recursion in programming is extremely powerful for solving programming problems.