Introduction to Recursion11 Oct 2017
While completing the set of videos from the second week of MIT’s Introduction to Computer Science and Programming Using Python course, I was introduced to recursion. I had heard of recursion before but I wanted to share my understanding of the topic.
Recursion is a technique used in programming to solve problems which fall under a divide and conquer paradigm. This paradigm revolves around the idea that the solution to a problem will depend on smaller solutions of the same problem. The most common application of recursion in computer science is a recursive function. A recursive function is when a function is called within the function definition.
Recursion is used to break a problem down to the simplest case which can be solved. As a result recursive functions have two properties associated with them. These properties are:
- Base case
- Recursive case
The base case will cause the function to exit if it is met. If the base case is not met, the recursive case is executed which should lead us one step closer to the base case.
Calculating the factorial of a number can be achieved using recursion. Any value that is passed to the function which is greater than 1 will reach the recursive case, where each function call will eventually reach the base case.
The expected return value from factorial (5) should be 120 since 54321 = 120. Going through a sample walkthrough of how this works should make it more clear. Using an example input of 5, the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120.
- factorial (5) = 5 * factorial (4)
- factorial (5) = 5 * (4 * factorial (3))
- factorial (5) = 5 * (4 * (3 * factorial (2)))
- factorial (5) = 5 * (4 * (3 * (2 * factorial (1))))
- factorial (5) = 5 * (4 * (3 * (2 * (1)))) = 120
In the first call of the function, the base case is not met so we call the factorial function again. The function calls continue until the base case is met. Once the base case is met, the function begins to return the values and break out of each function call. The final call returned a value that is equivalent to the mathematical calculation above.
Iteration vs Recursion
Iteration is very similar to recursion but it doesn’t require any function calls. The same recursive function for the factorial problem can be written as an iterative solution as well.
This is an equivalent function in recursion but requires some extra steps such as initializing a variable, defining a range for the iteration, and performing the product calculation.
Recursive functions are dangerous if the recursive calls do not eventually reach the base case. This can result in infinite recursion since each execution of the function will continue to call the function. Even if infinite recursion does not occur, a large amount of recursive function calls can overload the stack space and cause stack overflow **.
** In a future post, I will go over stack space and stack overflow.
Recursive functions are elegant solutions and are quite succint in nature. In the factorial example, the recursive implementation required no initialization for variables, no for loops and was easy to understand. This isn’t always the case with recursion and can be difficult to read if the problem which is being broken down is more complex. Recursive functions utilize more memory resources whereas iteration can be a more efficient approach with memory restrictions. Ultimately, the approach to take is dependent on the requirements and functionality of the program.