Hey Aspirant!!!!
In this blog let us understand and make our hands dirty by writing programs using Recursion.
The Contents of the article include:
What is Recursion?
Base Condition in Recursion
Why Recursion?
Programs using Recursion.
What is Recursion?
A recursion is a function that calls itself inside its function. This technique of calling function itself provides a way to break complicated problems down into simple problems which are easier to solve.
**Recursion calls **are stored in STACK fashion i.e. new function call on the TOP [LIFO - Last In First Out] this approach is called Recursion Stack.
Recursion Stack is stored in Heap Memory.
All the other Data structures like Arrays, Stack, Queues, maps, and Sets will occupy memory during Compilation.
Only Recursion will occupy space during Execution. Because the compiler will never tell whether the logic is correct or not, it will only check the syntax errors.
public int fact(int n){
if(n == 1 || n == 0){
return 1;
}
return n * fact(n-1);
}
This function will now get to know, I'm calling myself inside my function which is why I'm Recursion.
The sequence of the above function will be stored in the stack as:
fact(1) --> fact(2) --> fact(3) --> fact(4) -->fact(5) which is called STACK order which is stored in** HEAP**.
While the function is not finished it will remain in STACK
When the function finishes execution, it is removed from the stack and the flow of the program is restored to where the function is called.
Understanding recursion might take time but the easiest way to understand it better is by experimenting with how it works.
Recursion Syntax:
void methodName()
{
//code to be executed
methodName()
{
//calling same method
}
}
Base Condition in Recursion
A condition where our recursion will stop making new calls.
If there is no base condition, the function call will keep happening Stack will be filled and leads to StackOverFlow Error
Why Recursion?
Recursion helps in solving bigger or more complex problems simply.
We can convert the Recursion solution into iteration and vice versa.
In Recursion Space Complexity is not constant because of Recursive calls.
Recursion helps in breaking down bigger problems into smaller problems.
a. Can All Recursive code can be solved by Iteration?
- Yes
b. Can All Iterative code can be solved by Recursion?
- Yes
How to understand and approach a problem as a Recursion problem?
Identify if you can break down a problem into smaller problems.
Write the recurrence relation if needed, the formula which we can identify using recursion is known as the Recurrence Relation.
Base conditions will already be provided with the questions
Example Programs using Recursion
Program 1: Find nth Fibonacci number
static int fibo(int n){
if(n < 2){
return n;
}
return fibo(n - 1) + fibo(n - 2);
}
Input: num = 6
Output : 8
Program 2: Print linearly number from N
static int printLinearFromN(int num){
if(num == 0){
return num;
}
System.out.println(num);
return printLinearFromN(num - 1);
}
Input: num = 6
Output : 6 5 4 3 2 1
Program 3: Print linearly number from 1 to N
static void printLinearly(int num){
if(num == 0){
return;
}
printLinearly(num - 1);
System.out.println(num);
}
Input: num = 6
Output : 1 2 3 4 5 6
Program 4: Factorial of a number
static int fact(int n){
if(n <= 1){
return 1;
}
return n * fact(n - 1);
}
Input : 5
Output : 5 * 4 * 3* 2 * 1 = 120
Program 5: Sum of a given Digit or an Integer
static int sumOfInteger(int n){
if(n % 10 == 0){
return 0;
}
return (n % 10) + sumOfInteger(n / 10);
}
Input: 123
Output : 1 + 2 + 3 = 6
Program 6: Infinite Recursion
static void infiniteRecursion(int n){
if(n == 0){
return;
}
System.out.println(n);
infiniteRecursion(n--); // Infinite error
infiniteRecursion(--n); // for Input 5 , output - 5 4 3 2 1
}
Program 7: Reverse a Number
static int sum = 0;
static void reverseNumber(int n){
if(n == 0){
return;
}
int remainder = n % 10;
sum = sum * 10 + remainder;
reverseNumber(n / 10);
}
input : 5674
output : 4765
Program 8: count zero's in a number
static int countZero(int n, int count) {
if(n == 0) {
return count;
}
int remainder = n % 10;
if(remainder == 0) {
return countZero(n/10, count + 1);
}
return countZero(n/10, count);
}
input : 200800, 0
output : 4
Program 9: count the number of steps LeetCode:1342
static int numberOfSteps(int num, int steps) {
if(num == 0) {
return steps;
}
if(num % 2 == 0) {
return numberOfSteps(num/2, steps+1);
}
return numberOfSteps(num-1, steps+1);
}
input : 14
output : 6
Program 10: Print Triangle of * using Recursion
static void triangle(int row, int column) {
if(row == 0) {
return;
}
if(column < row) {
System.out.print("*");
triangle(row, column+1);
}else {
System.out.println();
triangle(row-1, 0);
}
}
input : 5
output :
*****
****
***
**
*
Program 11: Bubble sort using Recursion
static void bubbleSort(int[] arr, int row, int column) {
if(row == 0) {
return;
}
if(column < row) {
if(arr[column] > arr[column + 1]) {
// swap
int temp = arr[column];
arr[column] = arr[column + 1];
arr[column + 1] = temp;
}
bubbleSort(arr, row, column + 1);
}else {
bubbleSort(arr, row - 1, 0);
}
}
input:
int[] arr = {4, 3 , 5, 2, 1}; bubbleSort(arr, arr.length - 1, 0);
output: [1, 2, 3, 4, 5]
Program 12: String is palindrome or not using recursion
static boolean isPalindrome(String s, int i) {
if(i > s.length()/2) {
return true;
}
return s.charAt(i) == s.charAt(s.length() - i -1) &&
isPalindrome(s, i+1);
}
input : madam, 0
output : true
Program 13: Reverse String using recursion
static String recursiveMethod(String str){
if ((null == str) || (str.length() <= 1)){
return str;
}
return recursiveMethod(str.substring(1)) + str.charAt(0);
}
input : MyJava
output : avaJyM
Thank you for reading and spending time here. Please like the article, it will encourage me to write more such articles. Do share your valuable suggestions, I appreciate your honest feedback!!!