Recursion helps in solving larger complex problems by breaking them into smaller ones.
Let's look at an example of recursion.
package Recursion;
public class num {
public static void main(String[] args) {
print(1);
}
public static void print(int num){
System.out.println(num);
print(num + 1);
}
}
It goes into an infinite loop printing all the numbers continously.
Every function call takes up some space in the memory. Thus memory exceeds.
To prevent this we need a base condition.
A base condition is a simple if condition where the function will stop making new recursive calls.
package Recursion;
public class num {
public static void main(String[] args) {
print(1);
}
public static void print(int num){
if(num == 10){
return;
}
System.out.println(num);
print(num + 1);
}
}
The space complexity is not constant because of recursive function calls.
Recursion tree for printing first 5 numbers using recursion.
Fibonacci numbers
Recurrence relation for finding Fibonacci numbers:
Fibo(N) = Fibo(N - 2) + Fibo(N - 1)
Base Conditions:
Fibo(0) = 0, Fibo(1) = 1
package Recursion;
public class FibonacciNums {
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
System.out.print(fibonacci(i)+ " ");
}
}
public static int fibonacci(int n){
if(n <= 0){
throw new IllegalArgumentException("Enter a positive integer");
}
else if(n == 1){
return 0;
}
else if(n == 2){
return 1;
}
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
Factorial Of A Number
The recurrence relation for finding the factorial of a number is
Fact(n) = n * Fact(n - 1)
Base Condition:
Fact(0) = 1
package Recursion.Level1;
public class Factorial {
public static void main(String[] args) {
int ans = Fact(5);
System.out.println(ans);
}
public static int Fact(int n){
if(n == 0 || n == 1){
return 1;
}
return n * Fact(n - 1);
}
}
Sum Of All Digits
Recurrence Relation:
Sum(N) = N%10 + Sum(N/10)
Base Condition:
Sum(0) = 0
package Recursion.Level1;
public class SumOfDigits {
public static void main(String[] args) {
int ans = SumDigits(1234);
System.out.println(ans);
}
public static int SumDigits(int n){
if(n == 0){
return 0;
}
return n%10 + SumDigits(n / 10);
}
}
Product Of all Digits
Recurrence Relation:
Prod(N) = N%10 * Prod(N/10)
Base Condition:
Prod(1) = 1
package Recursion.Level1;
public class ProductOfDigits {
public static void main(String[] args) {
int ans = product(321);
System.out.println(ans);
}
public static int product(int n){
if(n % 10 == n){
return n;
}
return (n%10) * product(n/10);
}
}
Count Number Of Zeros
Base Condition:
N == 0
package Recursion.Level1;
public class CountZeros {
public static void main(String[] args) {
System.out.println(count(302100));
}
public static int count(int n){
return helper(n,0);
}
private static int helper(int n, int c){
if(n == 0){
return c;
}
int rem = n % 10;
if(rem == 0){
return helper(n/10, c+1);
}
return helper(n/10, c);
}
}
Number Of Steps
Given an integer num, return the number of steps to reduce it to zero. In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
Example 1: Input num = 14 Output: 6 Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
public class NumberOfSteps {
public static void main(String[] args) {
System.out.println(numberofsteps(14));
}
public static int numberofsteps(int num){
return helper(num, 0);
}
private static int helper(int num, int steps){
if(num == 0){
return steps;
}
if(num % 2 == 0){
return helper(num/2, steps + 1);
}
return helper(num - 1, steps + 1);
}
}