|
In this article:
- What is Recursion?
- Recursion Algorithms
- Types of Recursion
What is Recursion?
When a function is defined in the terms of the function itself, it is termed as Recursion. Recursion finds varied applications but most importantly in parsers of programming language compilers. The reason why recursion is important is that by only writing a small, finite function or computer program, one can produce an infinite number of designs or outputs.
Recursive algorithms
In computer programming languages, it is a common technique to divide a problem into small problems of the same kind in order to simplify the program. This is also called divide and conquer. This technique has been used to solve the biggest and hardest of problems and has resulted in many crucial algorithms.
Recursive functions are usually implemented using what is called a call stack. Under this technique, a unique copy (called an instance) of the recursive function is kept in memory every time a call to that function is made. These functions are placed upon a stack and executed one by one, finally yielding the desired result. This is the way most programming languages execute recursive functions or procedures. Recursion can act as a replacement for iteration (that is, looping). In the same way, an iterative function can replace a recursive function. This is done by using continuations.
Certain logical and functional programming languages only have recursion as the only method of looping available while others provide both, recursion and iteration. However, in languages recursion is the only method of looping or repetition, the recursion is technique is very powerful and efficient like iteration itself. Probably, the best example for recursion are the mu-recursive functions and Turing machines in the theory of computation that make the modern computer system a possibility. The 91 Function developed by John McCarthy is also an example of recursion.
Sometimes, recursion may prove to be a better way of implementing a certain algorithm. This is demonstrated by the recursive implementation of the Quicksort and Mergesort algorithms which results in lesser processing time. Operations on tree data structures such as sorting and searching can also be implemented through recursion especially if the size of the tree (that is, its length) is not known. Additionally, some mathematical equations can be efficiently solved using recursion. This includes the Newton's method where the first input to the method is the root of a function and the calculated result acts an input to the method again. This process goes on repeating till a satisfactory value is not reached. Thus, it can be implemented with the help of recursion.
Types of recursive functions
Recursive functions maybe classified as being tail recursive, double-test tail recursive, single-test tail recursive or augmenting recursive. These have been explained below:
- Tail recursive function
This type of recursive function is one where the function runs a number of tests one after the other and if a particular test ends up as being true, the function returns a particular value. However, if all the tests fail, that is, they end up being negative or false, the functions calls itself again but with a reduced or changed input value. The value returned by the last call of the function is the desired result and is called the return value of the whole function.
- Double-Test Tail Recursion
This is a variation of tail recursion that is found on a large scale. This type of a recursive function checks for two things. First, it checks if the function has reached its end. This is then followed by checking if a result was reached. If both of these tests turn out to be false, it calls itself again.
- Single-Test Tail Recursion
In this type of recursion, we leave out the first test done by a double-test tail recursive function. This is done to prevent processing and execution time when we are sure that the function will reach a certain desired result anyhow.
- Augmenting Recursion
This type of recursion is unique in the sense that in this, the value input back into the function is different from the value that is received by the previous function call. This means that the return value of a particular function will be increased before it is forwarded to the next function call as input.
|
