We have learned that many algorithms solving different problems have repetitive nature and so far we have always used loops to implement solutions to these solutions. In this final lecture, we introduce an alternative programming paradigm called recursion, where we can define a solution as a function of itself, and repetitively invoke the same method such that it continues execution until the problem is solved.
The Fibonacci sequence
A very well-known example of functions that are functions of themselves is observed very early on in arithmetic studies. In this short video, we introduce the experiments of Fibonacci and how he came up with the famous sequence of numbers, also called as the Fibonacci sequence, and how we can approach the computation of the Fibonacci numbers with recursion.
Exercise 1: Power
Another illustrative example is to solve a power equation x^n recursively. In this exercise, try implementing a power method that takes the exponent of a given base with the given number, using only the same method recursively in your computation.
Solution
Let’s try to examine the nature of the problem over an example, such as the value of 6^3. The exponent of a number is given as the product of the number with itself the exponent number of times, such that 6^3 is 6*6*6. If we would like to represent this problem recursively, we can use the decomposition method to represent the problem as a function of itself. Thus, 6^3 can be represented as 6*6^2, where 6^2 can be represented as 6*6^1. We can see the problem naturally continues to decompose, until the exponent is 1. Thus, we will represent the closed form formula as x^n = x*x^(n-1). The software implementation for the recursive power computation method can be seen as below.
Exercise 2: Reverse a string
A simpler example of a recursive algorithm for a function used to reverse a string:
- If the original string is only one character long, the reversed form is the same as the original e.g., “e” backwards is “e”
- Otherwise, return the last character of the original string concatenated to the reversed version of the remainder (excluding the last character) e.g., “rain” backwards is (“n” + backwards(“rai”))
Solution
Pattern for implementing recursive algorithms
Most problems that can be solved with loops can also be solved with recursion, and this often allows us to represent solutions in a simpler and more elegant way. If you like recursion, you can try to integrate it more in your programming solutions in the future that are of the repetitive type to save time and complexity in your programming process.