Java for DSA — Functions & Recursion
4. Functions & Recursion
Why this matters for DSA Functions break complex algorithms into manageable, modular pieces. In Java, understanding how parameters are passed (Pass-by-Value) avoids bugs where arrays/objects are unexpectedly modified. Additionally, recursion is the core driver for Tree, Graph (DFS), Backtracking, and Dynamic Programming algorithms.
4.1 Defining Methods
A method is a block of code containing statements that execute when it is called.
public class Calculator {
// 1. Standard method returning a single value
public static int add(int a, int b) {
return a + b;
}
// 2. Returning multiple values using an array
public static int[] getMinMax(int[] arr) {
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
return new int[]{min, max}; // returns both as a 2-element array
}
}
Java is Pass-by-Value Java passes arguments by value, but for objects (like arrays or lists), the "value" passed is the reference to the memory.
- Modifying a primitive variable inside a method does NOT change it outside.
- Modifying the contents of an array or list inside a method DOES change it outside.
public static void modify(int x, int[] arr) {
x = 100; // Outer x remains unchanged
arr[0] = 100; // Outer arr[0] is modified!
}
4.2 Method Overloading (Simulating Default Parameters)
Java does not support default arguments natively. Instead, you use method overloading (methods with the same name but different parameter list definitions) to achieve the same result.
// Method with 1 parameter (behaves like a default setting)
public static void greet(String name) {
greet(name, "Hello"); // calls the overloaded method below
}
// Method with 2 parameters
public static void greet(String name, String greeting) {
System.out.println(greeting + ", " + name);
}
4.3 Static vs Instance Methods
class Solver {
// Static - accessed via the Class name directly, no object instantiation needed
public static int add(int a, int b) {
return a + b;
}
// Instance - requires an object instance to be created first
public int multiply(int a, int b) {
return a * b;
}
}
// Calling Static vs Instance:
int sum = Solver.add(3, 4); // Static call
Solver solverInstance = new Solver();
int product = solverInstance.multiply(3, 4); // Instance call
4.4 The Math Class
Java's built-in Math class contains optimized operations essential for math-based DSA problems:
Math.abs(-5); // 5 (absolute value)
Math.min(2, 5); // 2 (minimum value)
Math.max(2, 5); // 5 (maximum value)
Math.pow(2, 3); // 8.0 (returns double!)
Math.sqrt(16); // 4.0 (square root, returns double!)
Math.floor(3.7); // 3.0 (rounds down)
Math.ceil(3.2); // 4.0 (rounds up)
Math.round(3.5); // 4 (rounds to nearest integer, returns long/int)
// Useful Constants
Math.PI; // 3.141592653589793
4.5 Recursion & The Call Stack
Recursion is a process in which a method calls itself to solve smaller subproblems of the same problem.
The 2 Golden Rules of Recursion:
- Base Case: The condition under which the function stops calling itself.
- Recursive Step: The logic that breaks the problem into a smaller case and calls itself.
// Example: Computing Factorial (N!)
public static int factorial(int n) {
// 1. Base Case
if (n <= 1) {
return 1;
}
// 2. Recursive Case
return n * factorial(n - 1);
}
Call Stack visualization for factorial(3):
factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) returns 1 (Base Case reached)
factorial(2) resumes: 2 * 1 = 2
factorial(3) resumes: 3 * 2 = 6
Space Complexity of Recursion
Each recursive call adds a frame to Java's stack memory. The stack space is proportional to the maximum recursion depth. If recursion depth is too high, Java throws a StackOverflowError.
| Scenario | Stack Depth / Space Complexity |
|---|---|
Linearly decrementing (n to 0) | auxiliary stack space |
Dividing in half (n to n/2) | auxiliary stack space |
Practice Drill
// Try implementing these:
// 1. Write a method to check if a number is prime.
// 2. Write a recursive method to calculate the sum of digits of a positive number (e.g. 123 -> 6).
// 3. Write a recursive method to reverse a string.
// 4. Implement recursive binary exponentiation (Math.pow equivalent for integer exponents in O(log n) time).
💡 Click for Solutions
public class FunctionsDrill {
public static void main(String[] args) {
// 1. Prime check
System.out.println("Is 17 prime? " + isPrime(17)); // true
// 2. Sum of digits (recursive)
System.out.println("Sum of digits of 1234: " + sumOfDigits(1234)); // 10
// 3. Reverse a string (recursive)
System.out.println("Reverse of 'abc': " + reverseString("abc")); // "cba"
// 4. Binary exponentiation: 2^10
System.out.println("2^10 = " + power(2, 10)); // 1024
}
// 1. Prime checking helper
public static boolean isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
// 2. Sum of digits recursion
public static int sumOfDigits(int n) {
if (n == 0) {
return 0;
}
return (n % 10) + sumOfDigits(n / 10);
}
// 3. Reverse string recursion
public static String reverseString(String str) {
if (str.isEmpty() || str.length() == 1) {
return str;
}
return reverseString(str.substring(1)) + str.charAt(0);
}
// 4. O(log n) Recursive Power (Binary Exponentiation)
public static long power(long base, int exp) {
if (exp == 0) return 1;
long half = power(base, exp / 2);
if (exp % 2 == 0) {
return half * half;
} else {
return base * half * half;
}
}
}
← Control Flow | Next → Arrays & Collections