Recursion in Golang
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code
Source: Wikipedia
To understand Recursion in a visual format we will take the example of the Russian dolls.
At first, we just see one figurine but when we open the top half of it we see another slightly smaller, Russian doll.
We can remove that doll and separate its top and bottom halves and we see yet another, even smaller, Russian doll. This keeps on going till the point we find the smallest doll which does not open. This is where we finally stop.
The above example comes close to understanding the Recursion algorithm. Where the problem to be solved is broken down into multiple smaller problems, to a point that it cannot be broken down any further. Every recursion must have at least one base case, at which the recursion does not recur.
Recursion is the concept of well-defined self-reference. In other words, it is the technique of making a function call itself in a case when the function does not call itself recursively. This case is called the Base Case which is extremely important! Without the base case, the function will keep calling itself and will never stop. There could be one or more base cases.
Thus, a recursive function usually has a certain structure:
1. A base case, which does not call the function itself (the exit point)
2. A recursive step, which calls the function itself and moves closer to the base case.
Even with the right structure, we still need to be careful with infiniteness.
Types of Recursion:
- single recursion: contains only a single self-reference
- multiple recursion: contains multiple self-references
Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.
Example 1: Factorial Calculation
The expression to calculate the factorial of n (n≥ 0) is n! = n * (n-1)!
Which is the recursive expression of the factorial calculation.
n! equals 1 when n = 0.
Example 2: Exponentiation Calculation
Going with the assumption that x > 0 and n >= 0
Where x is the base of the logarithm and n is the exponent
We can easily calculate x raised to the power of n with a linear recursion.
Both examples 1 and 2 are a type of linear recursion in a single base case since it makes one recursive call at a time and only has one exit condition.
Example 3: Palindrome Identification
A palindrome is a word that is spelled the same forward and backward. For example, the rotor is a palindrome, but the motor is not. It’s a sequence of letters that reads the same forward and backward. Hence any string that contains just one letter is by default a palindrome but an empty string is also a palindrome since it reads the same from front and back. For a sequence with more than one letter, the first and the last letter should be the same.
In the above example 3 there are two base cases for termination of the recursion. At least one base case is required to avoid the infinite loop. There can be multiple base cases as per the algorithm.
Example 4: Fibonacci Sequence
In the Fibonacci sequence, each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors omit the initial terms and start the sequence from 1 and 1 or from 1 and 2. Starting from 0 and 1, the next few values in the sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
We can define a function F(n) that calculates the nth Fibonacci number.
First, the base cases are: F(0) = 1 and F(1) = 1.
Now, the recursive case: F(n) = F(n-1) + F(n-2).
The above recursion is called multiple recursion or binary recursion since it makes two recursive calls instead of one.
Fibonacci recursion makes a number of calls that are exponential in k. In other words, using binary recursion to compute Fibonacci numbers is very inefficient. Compare this problem with binary search, which is very efficient in searching items, why is this binary recursion inefficient? The main problem with the approach above is that there are multiple overlapping recursive calls.
Conclusion
Recursion can be an elegant way to solve a problem, and many algorithms lend themselves to recursive solutions. However, recursive algorithms can be inefficient in terms of both time and space.
Recursion consumes stack space. Every recursive method call produces a new instance of the method, one with a new set of local variables. The total stack space used depends upon the level of nesting of the recursion process, and the number of local variables and parameters. Recursion may perform redundant computations. Consider the recursive computation of the Fibonacci sequence.
In sum, one has to weigh the simplicity of the code delivered by recursion against its drawbacks as described above. When a relatively simple iterative solution is possible, it is definitely a better alternative. Sometimes the best way to improve the efficiency of a recursive algorithm is to not use recursion at all.
References
https://en.wikipedia.org/wiki/Recursion_(computer_science)
https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion
https://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm
