Multiple Recursion Examples in Java
Multiple recursion occurs when a method calls itself more than once in its body. Examples
include tree traversal, Fibonacci calculation, and recursive drawing algorithms.
1. Fibonacci Series (Naive Recursive Approach)
public class Fibonacci {
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // multiple recursion
}
public static void main(String[] args) {
int n = 10;
for (int i = 0; i < n; i++) {
[Link](fib(i) + " ");
}
}
}
Explanation: Each call to fib(n) may call fib(n-1) and fib(n-2).
2. Factorial Sum with Two Recursive Calls
public class FactorialSum {
static int factorialSum(int n) {
if (n == 1) return 1;
return n + factorialSum(n - 1) + factorialSum(n - 2);
}
public static void main(String[] args) {
int n = 5;
[Link](factorialSum(n)); // Multiple recursive calls
}
}
Explanation: Demonstrates multiple recursive calls within the sum computation.
3. Binary Tree Traversal (Preorder)
class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}
public class BinaryTree {
static void preorder(Node root) {
if (root == null) return;
[Link]([Link] + " ");
preorder([Link]); // recursive call
preorder([Link]); // recursive call
}
public static void main(String[] args) {
Node root = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);
preorder(root);
}
}
Explanation: Each node calls recursion on left and right subtrees.
4. Sum of All Nodes in Binary Tree
static int sumTree(Node root) {
if (root == null) return 0;
return [Link] + sumTree([Link]) + sumTree([Link]);
}
Explanation: Multiple recursion on both left and right subtrees.
5. Tower of Hanoi
public class TowerOfHanoi {
static void solve(int n, char from, char to, char aux) {
if (n == 1) {
[Link]("Move disk 1 from " + from + " to " + to);
return;
}
solve(n - 1, from, aux, to);
[Link]("Move disk " + n + " from " + from + " to " + to);
solve(n - 1, aux, to, from);
}
public static void main(String[] args) {
int n = 3;
solve(n, 'A', 'C', 'B');
}
}
Explanation: Recursive call twice for moving n-1 disks before and after moving the nth disk.
6. Counting Paths in a Grid (m×n)
public class GridPaths {
static int countPaths(int m, int n) {
if (m == 1 || n == 1) return 1;
return countPaths(m - 1, n) + countPaths(m, n - 1); // multiple
recursion
}
public static void main(String[] args) {
[Link](countPaths(3, 3)); // 6 paths
}
}
Explanation: Each cell can go down or right, leading to two recursive calls.
7. Generate All Binary Strings of Length n
public class BinaryStrings {
static void generate(String str, int n) {
if (n == 0) {
[Link](str);
return;
}
generate(str + "0", n - 1); // first recursive call
generate(str + "1", n - 1); // second recursive call
}
public static void main(String[] args) {
generate("", 3); // outputs all 8 binary strings
}
}
Explanation: Each call splits into two choices: 0 or 1.
8. Print All Subsequences of a String
public class Subsequences {
static void printSubseq(String str, String result, int index) {
if (index == [Link]()) {
[Link](result);
return;
}
printSubseq(str, result + [Link](index), index + 1); // include
printSubseq(str, result, index + 1); // exclude
}
public static void main(String[] args) {
printSubseq("abc", "", 0); // prints 8 subsequences
}
}
Explanation: Multiple recursion branching for include/exclude each character.
9. Recursive Merge of Two Lists
class Node2 {
int data;
Node2 next;
Node2(int data) { [Link] = data; }
}
public class MergeLists {
static Node2 merge(Node2 a, Node2 b) {
if (a == null) return b;
if (b == null) return a;
if ([Link] < [Link]) {
[Link] = merge([Link], b);
return a;
} else {
[Link] = merge(a, [Link]);
return b;
}
}
}
Explanation: Multiple recursion occurs when choosing head of merged list.
10. Recursive Fractal Pattern (Koch Curve Example)
public class KochFractal {
static void koch(int n, String str) {
if (n == 0) {
[Link](str);
return;
}
koch(n - 1, "F");
[Link]("+");
koch(n - 1, "F");
[Link]("-");
koch(n - 1, "F");
}
public static void main(String[] args) {
koch(2, "F"); // Fractal pattern output
}
}
Explanation: Recursive call three times at each step to create fractal pattern.
✅ Key Observations
• Multiple recursion is often used in:
o Trees (preorder, postorder, sum)
o Graphs (DFS)
o Combinatorics (subsets, permutations)
o Fractals or recursive drawing
• Each recursion multiplies the number of function calls exponentially in naive
implementations.
• Memoization or iterative DP can optimize some examples (e.g., Fibonacci).