All you need to know about Recursion
Let’s have a look at what Recursion and Recursive functions are!
What is Recursion?
When a function is calling itself directly or indirectly is known as Recursion and the function is referred to as Recursive function.
Structure of a Recursive Function
There are three main components of the recursive function:
- Function call inside the function (function should be calling itself).
- Base Condition
- Function return type
Type function_name(params){
if (<base_condition>){
--------
--------
function_name(params')
--------
--------
}
}Base condition is an important part of the Recursive Function which helps to terminate the function at some point. If the base condition is not proper it (that is non-terminating) may end up creating an infinite loop.
Difference between iterative function and recursive function
A recursive function has two segments of a code that is ascending and descending whereas iterative has only ascending segment of the code.
Types of Recursion
- Tail Recursion — When the recursive call is the last statement of the recursive function it is referred to as Tail Recursion
function_name(params) {
if (<base_condition>) {
-----
-----
-----
function_name(params);
}
}All the operations in the Tail Recursion are done while calling time and no operations are performed in returning time.
- Head Recursion — When the recursive call is the first statement of the recursive function it is known as Head Recursion.
function_name(params) {
if (<base_condition>) {
function_name(params);
-----
-----
-----
}
}All the operations in the Head Recursion are done while returning. No code operations are done at the time of calling.
- Tree Recursion — When a recursive function calls itself more than once in the function it is referred to as Tree Recursion.
function_name(params) {
if (<base_condition>) {
function_name(params);
-----
-----
function_name(params);
-----
-----
}
}- Indirect Recursion — When one function calls the other function and the other calls back the first forming a loop is called Indirect Recursion. More than 2 functions may be involved.
function_name1(params) {
if ( <base_condition>) {
----
----
function_name2(params);
----
}
}function_name2(params) {
if ( <base_condition>) {
----
----
function_name1(params);
----
}
}
- Nested Recursion — When a recursive call is passed as a parameter to a recursive function it is said to be a Nested Recursion
function_name(params) {
if (<base_condition>){
----
----
function_name(function_name(params));
----
}
}Facts about Recursion
- Some compilers try converting your tail recursion into object code and eventually into loops reducing the time complexity of the programs.
- Recursion uses the stack for its functioning
- The tree data structure is mostly used with recursion for all the operations.
I will love to hear feedback at @HimanshuKhaita4 for the content above. Also, I will be posting 5 words for every weak related to different topics (mostly tech and finance).
