Recursion is when a function calls itself within its definition. This can be very useful in solving complex problems by breaking it up into smaller pieces. For example, if you wanted to count the non-list elements in a nested list, you could write a recursive function that first checks if what it's given is a list. If it isn't a list, the function will add 1 to its return value. If it is a list, the function will put each element of the list through itself again, and repeat the process just illustrated. This function could be written as:
def non_list(lst):
return sum([non_list(val) if isinstance(val, list) else 1 for val in lst])
(note: this function only works if the parameter lst is a list)
The function works by using a list comprehension and repeatedly calling itself until the property of lst not being a list is met. Many recursive functions could also be written using while or for loops. In fact, using that method also uses less memory. However, recursive functions often offer a more elegant solution to the problem. They can also be written without using a list comprehension. For example, the above function could also be written as:
def non_list(lst):
nonlst = []
def counter(lst2):
if isinstance(lst2, list):
for a in lst2:
counter(a)
else:
nonlst.append(1)
counter(lst)
return sum(nonlst)
This is considerably bulkier and uses a nested function but works nonetheless. In general, a recursive algorithm should have a base case that it tries to get all of its parameters to approach (in this case the base case is having type(lst) != list) and to do this it keeps calling itself recursively. This works because the recursive function works backwards in a sense by reducing all of its elements to the most basic case and then combining all of the values once they're in that form to give the correct return value.
