Recursion
Recursion is the process of repeating items in a self-similar way. If a function has a function call to itself then it is said to be a recursive function.
How recursion can be used effectively?
Recursion can be useful if sub-problems of a problem are repetitive and can be useful if the problem has many branches and it's hard for an iterative approach.
Stack overflow error in recursion
Every recursive approach has a base case and recursive steps with backtracking to it. If a function doesn't reach the base case stack overflow problem may arise.
Direct and Indirect recursion
Direct recursion is approaching when the same function calls itself. This is like one step recursion the function makes a call within its own body.
Ex:
class App {
public static void main(String[] args) {
// calling indirectRecursion1()
}
static int directRecursion(int n) {
// function calls indirectRecursion1
// indirectRecursion1(n);
// some code
}
}
Indirect recursion is approach when the function calls another function recursively.
class App {
public static void main(String[] args) {
// calling indirectRecursion1()
}
static int indirectRecursion1(int n) {
// function calls indirectRecursion2
// indirectRecursion1(n);
// some code
}
static int indirectRecursion2(int n) {
// function calls indirectRecursion1
// indirectRecursion1(n);
// some code
}
}
What is tail recursion?
A recursive function is tail recursive when recursive call is the last thing executed by the function.
class App {
public static void main(String[] args) {
tailRecursion(2);
}
static void tailRecursion(int n) {
if (n < 0) {
return;
}
System.out.println(n);
tailRecursion(n - 1);
}
}
Non-tail recursion
A recursive function is tail recursive when recursive call is executed by the function at the beginning itself.
class App {
public static void main(String[] args) {
nonTailRecursion(2);
}
static void nonTailRecursion(int n) {
if (n < 0) {
return;
}
nonTailRecursion(n - 1);
System.out.println(n);
}
}
How memory is allocated to recursion?
When any function is called from the main function, the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.
There are a lot of recursion examples but this example is considered as a simple one with just printing the variable given a number of times.
Ex:
class App {
public static void main(String[] args) {
Recursion(2);
//The value 2 is passed to recursive function
}
static void Recursion(int n) {
//In every recursion call it checks if n is less than zero and acts as a baser condition.
if (n < 0) {
return;
}
// prints the current value of n
System.out.println(n);
//n is further decremented by one
// It again calls the recursive function with the decremented value.
Recursion(n - 1);
}
}
I hope you guys liked this article and here are some articles you may like:
0 Comments