Practice Problems & Solutions
Practice these problems to solidify your understanding of recursion!
Problem 1: Calculate Sum of Numbers
Problem: Write a recursive function to calculate the sum of first n natural numbers.
Input: n = 5
Output: 15 (1 + 2 + 3 + 4 + 5 = 15)
Problem 2: Find Factorial
Problem: Write a recursive function to calculate n!
Input: n = 5
Output: 120 (5! = 5 × 4 × 3 × 2 × 1 = 120)
Problem 3: Check if Array is Palindrome
Problem: Write a recursive function to check if an array reads the same forwards and backwards.
Input: [1, 2, 3, 2, 1]
Output: true
Input: [1, 2, 3, 4, 5]
Output: false
Problem 4: Count Occurrences
Problem: Count how many times a number appears in an array.
Input: arr = [1, 2, 3, 2, 4, 2], target = 2
Output: 3
Problem 5: String Reversal
Problem: Reverse a string using recursion.
Input: "Hello"
Output: "olleH"
Problem 6: Power Function
Problem: Calculate base^exponent using recursion.
Input: base = 2, exponent = 5
Output: 32
Problem 7: Fibonacci Sequence
Problem: Find the nth number in Fibonacci sequence.
Input: n = 6
Output: 8 (Sequence: 0, 1, 1, 2, 3, 5, 8...)
Problem 8: Binary Search
Problem: Search for a target value in a sorted array using binary search (recursively).
Input: arr = [1, 3, 5, 7, 9, 11], target = 7
Output: 3 (index of target)
Problem 9: Get All Divisors
Problem: Find all divisors of a number recursively.
Input: n = 12
Output: [1, 2, 3, 4, 6, 12]
Problem 10: Sum of Array Elements
Problem: Find the sum of all elements in an array recursively.
Input: [2, 4, 6, 8]
Output: 20
Solutions (Try Before Checking!)
Problem 1: Sum of Numbers
public static int sumOfNumbers(int n) {
// Base case
if (n == 0) {
return 0;
}
// Recursive case
return n + sumOfNumbers(n - 1);
}
// Or using mathematical formula recursion
public static int sumOfNumbersFormula(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return n + sumOfNumbersFormula(n - 1);
}
Complexity:
- Time: O(n)
- Space: O(n) - call stack
Problem 2: Factorial
public static int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
Complexity:
- Time: O(n)
- Space: O(n) - call stack
Problem 3: Array Palindrome
public static boolean isPalindrome(int[] arr) {
return isPalindromeHelper(arr, 0, arr.length - 1);
}
private static boolean isPalindromeHelper(int[] arr, int left, int right) {
// Base case: pointers met or crossed
if (left >= right) {
return true;
}
// Check if elements match
if (arr[left] != arr[right]) {
return false;
}
// Recursive case: move pointers closer
return isPalindromeHelper(arr, left + 1, right - 1);
}
Complexity:
- Time: O(n)
- Space: O(n) - call stack
Problem 4: Count Occurrences
public static int countOccurrences(int[] arr, int target, int index) {
// Base case: reached end of array
if (index == arr.length) {
return 0;
}
// Recursive case
int count = (arr[index] == target) ? 1 : 0;
return count + countOccurrences(arr, target, index + 1);
}
// Usage: countOccurrences(arr, 2, 0)
Complexity:
- Time: O(n)
- Space: O(n) - call stack
Problem 5: String Reversal
public static String reverse(String s) {
// Base case: empty or single character
if (s.length() <= 1) {
return s;
}
// Recursive case: reverse rest + first character
return reverse(s.substring(1)) + s.charAt(0);
}
// More efficient:
public static String reverseEfficient(String s) {
return reverseHelper(s, 0, s.length() - 1);
}
private static String reverseHelper(String s, int left, int right) {
if (left >= right) {
return s;
}
// Would need char array for true reversal
return reverseHelper(s, left + 1, right - 1);
}
Complexity:
- Time: O(n²) due to substring operations
- Space: O(n) - call stack
Problem 6: Power Function
public static int power(int base, int exponent) {
// Base case
if (exponent == 0) {
return 1;
}
// Recursive case
return base * power(base, exponent - 1);
}
// More efficient with divide and conquer
public static int powerOptimized(int base, int exponent) {
if (exponent == 0) {
return 1;
}
int half = powerOptimized(base, exponent / 2);
if (exponent % 2 == 0) {
return half * half;
} else {
return base * half * half;
}
}
Complexity:
- Simple: Time O(n), Space O(n)
- Optimized: Time O(log n), Space O(log n)
Try These First!
- Implement the solutions above
- Test with various edge cases (n=0, n=1, large n)
- Identify the base case and recursive case in each
- Calculate time and space complexity
- Compare iterative vs recursive approaches
Good luck! 🚀