Lesson 6: What is Recursion?

Introduction to Recursion

Recursion is a programming style where a function calls itself multiple times until a condition is satisfied.

Example One example of recursion is reversing an array. In this case, we switch the first and last array elements and subsequently call this reverse function for the remainder of the array.

In the example, we are first presented with an array from 10 to 16. On each nth step, we switch the first and last element with each other until the full array is reversed.

Code

In Python code, the program looks like this:

def arrayReversal(Arr, begin, end):
    while begin < end:
        Arr[begin], Arr[end] = Arr[end], Arr[begin]
        begin += 1
        end -= 1 

# Driver function to test above function
Arr = [10,  11, 12, 13, 14, 15]
print(Arr)
arrayReversal(Arr, 0, 5)
print("Reversed list is")
print(Arr)

As with any recursive method, this example has a base case which tells the function to no longer call itself. The base case in the reversal of an array is when the begin variable is no longer less than the end variable.

NOTE: Any recursive algorithm can also be written iteratively as an alternative.