Basic Recursion
Sum of First N Numbers
class Solution {
public int NnumbersSum(int N) {
if (N == 0) return 0;
return N + NnumbersSum(N - 1);
}
}This is a recursive function to calculate the sum of the first N natural numbers. The base case is when N is 0, where it returns 0. Otherwise, it returns N plus the sum of the first N-1 numbers.
Time Complexity: O(N), as the function calls itself N times.
Space Complexity: O(N) due to the recursion stack depth.
Factorial of a Given Number
class Solution {
public long factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
}This recursive function calculates the factorial of n. The base case returns 1 if n is 0. The recursive step is n multiplied by the factorial of n-1.
Time Complexity: O(n), as it makes n recursive calls.
Space Complexity: O(n) for the recursion stack.
Sum of Array Elements
class Solution {
public int arraySum(int[] nums) {
return recur(nums, 0);
}
public int recur(int[] nums, int n) {
if (n == nums.length) return 0;
return nums[n] + recur(nums, n + 1);
}
}The sum of array elements is found recursively. A helper function recur is used, which takes the array and the current index n. The base case is when n reaches the end of the array. The recursive step adds the element at the current index to the sum of the rest of the array.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n) for the recursion stack depth.
Reverse a String I
class Solution {
public ArrayList<Character> reverseString(ArrayList<Character> s) {
int left = 0, right = s.size() - 1;
return recur(s, left, right);
}
private ArrayList<Character> recur(ArrayList<Character> s, int left, int right) {
if (left >= right) return s;
Character temp = s.get(left);
s.set(left, s.get(right));
s.set(right, temp);
return recur(s, left + 1, right - 1);
}
}The string (as a list of characters) is reversed in-place using a recursive helper function that implements a two-pointer swap. The base case is when the left and right pointers meet or cross. In the recursive step, it swaps the characters at the left and right indices and calls itself for the inner part of the list.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) due to the recursion stack.
Check if String is Palindrome or Not
class Solution {
public boolean palindromeCheck(String s) {
int left = 0;
int right = s.length() - 1;
return recur(s, left, right);
}
private boolean recur(String s, int left, int right) {
if (left >= right) return true;
if (s.charAt(left) != s.charAt(right)) return false;
return recur(s, left + 1, right - 1);
}
}This recursive approach checks for a palindrome by comparing characters from both ends of the string. The base case for the recursion is when the two pointers left and right meet or cross each other. If the characters at the current pointers do not match, it returns false.
Time Complexity: O(n), where n is the string length.
Space Complexity: O(n) for the recursion stack.
Check if a Number is Prime or Not
class Solution {
public boolean checkPrime(int num) {
if (num == 1) return false;
return checkPrime(num, 2);
}
private boolean checkPrime(int num, int divisor) {
if (divisor * divisor > num) return true;
if (num % divisor == 0) return false;
return checkPrime(num, divisor + 1);
}
}This is a recursive implementation of trial division to check for primality. The helper function tests divisibility starting from divisor=2. The recursion stops and returns true if the divisor exceeds the square root of num. It returns false if a divisor is found.
Time Complexity: O(sqrt(num)), as it checks divisors up to the square root of num.
Space Complexity: O(sqrt(num)) due to the depth of the recursion stack.
Reverse an array
class Solution {
public int[] reverseArray(int[] nums) {
int left = 0;
int right = nums.length - 1;
return reverseArray(nums, left, right);
}
private int[] reverseArray(int[] nums, int left, int right) {
if (left >= right) return nums;
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
return reverseArray(nums, left + 1, right - 1);
}
}This function recursively reverses an array in-place. It uses a two-pointer approach, where elements at the left and right indices are swapped. The recursive call then moves the pointers closer to the center.
Time Complexity: O(n), for n/2 swaps.
Space Complexity: O(n) for the recursion stack.
Check if the Array is Sorted II
class Solution {
public boolean isSorted(ArrayList<Integer> nums) {
if (nums.size() == 1) return true;
int pos = 1;
return isSorted(nums, pos);
}
private boolean isSorted(ArrayList<Integer> nums, int pos) {
if (pos == nums.size()) return true;
if (nums.get(pos - 1) > nums.get(pos)) return false;
return isSorted(nums, pos + 1);
}
}This recursively checks if an array is sorted. The function isSorted is called with the current position pos. The base case is when pos reaches the end of the array. The recursive step checks if the previous element is greater than the current one.
Time Complexity: O(n), as it traverses the array.
Space Complexity: O(n) for the recursion stack.
Sum of Digits in a Given Number
class Solution {
public int addDigits(int num) {
if (num < 10) return num;
int digitSum = 0;
while (num > 0) {
digitSum += num % 10;
num /= 10;
}
return addDigits(digitSum);
}
}This function calculates the digital root of a number. It iteratively sums the digits of num, and then recursively calls itself with the sum until the number is a single digit.
Time Complexity: O(log n). The number of recursive calls is very small, and the while loop runs for each digit.
Space Complexity: O(log n) for the recursion stack, though it will be very shallow in practice.
Fibonacci Number
class Solution {
public int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
}This is the classic, unoptimized recursive solution for the Fibonacci sequence. The base cases are n=0 and n=1. The recursive step is the sum of the previous two Fibonacci numbers, fib(n-1) + fib(n-2).
Time Complexity: O(2^n). This is highly inefficient because it recomputes the same values many times, leading to an exponential number of calls.
Space Complexity: O(n) for the maximum depth of the recursion stack.