Recursion in computer science is the method of calling a function within it's own body. Recursion is used in programming when the solution to a problem involves knowing the solution of a simpler problem of the same kind. For example lets consider a simple function that returns the factorial of an integer n. This function could be implemented as follows:
def factorial(n):
x = 1
for i in range(1, n + 1):
x = x * i
return x
Here the function multiplies all integers from 1 to n and returns the result. But the function can also be implemented recursively as follows:
def factorial(n):
return n * factorial(n - 1) if n > 0 else 1
Notice how the function now includes a call on itself in the body. The function here multiplies n with the factorial of n - 1 unless n is 0 in which case the function would return 1. Lets trace a few calls on this function:
>>> factorial(0) # The if statement evaluates to false so the else clauseis returned 1 >>> factorial(1) # The if statement evaluates to true so 1 is multiplied by factorial(0) 1 >>> factorial(2) # 2 is multiplied by factorial(1) 2 >>> factorial(3) # 3 is multiplied by factorial(2) 6
Now lets talk about the makeup of a recursive function. A recursive function contains a base case or a terminating case that breaks the chain of recursion. In the factorial function the base case would be when n is equal to 0 as no recursion occurred in the evaluation. All other cases are recursion cases where a chain of recursion runs until the base case is reached.
The function factorial could be implemented easily without having to use recursion as in the first implementation of the function above. However more elaborate recursive functions could be very difficult to implement without the use of recursion. For example a function that sums the numbers of a possibly nested list could be implemented easily using recursion which would otherwise be a challenging task. The function can be implemented as follows:
def sum_list(L: list) -> 'num':
"""
Return the sum of the elements of L.
>>> sum_list([1, 2, 3])
6
>>> sum_list([1, [2, 3, [4]], 5])
15
"""
return sum( # sum of sum of sublists or non-list elements themselves
[sum_list(x) if isinstance(x, list) else x for x in L])
Finally recursion can also be used to define abstract data types. For example a Tree is an abstract data type that is made up of nodes connected to each other by edges where each node has only one parent. A tree consists of a root and possibly one or more children where each child is a tree itself. Another ADT that is based on recursion is a Linked list which is also made up of nodes where each node points to the next node in the list and each node contains a value. A linked list can either be an empty list or a node pointing to another linked list.
