Recursion is the process of solving a problem by reducing it to smaller versions of itself. A recursive function is an algorithm which is expressed in terms of a smaller version of itself.
A very good example of recursion is the factorial function. The factorial of a nonnegative integer n
, is defined as follows:
0! = 1
n! = n(n  1)! for n > 0
n!
is defined in terms of (n  1)!
, and the (n  1)!
is definde as follows:
(n  1)! = 1, if (n  1) = 0
(n  1)! = (n  1)(n  2)! if (n  1) > 0
For example, 3!
is
 Since
3 > 0
, it is3×2!
.  Since
2 > 0
,2!
is2×1!
, and3!
becomes `3×2×1!.  Since
1 > 0
,1!
is1×0!
, and3!
becomes3×2×1×0!
 Since
0!
is 1, we have3! = 3×2×1×1 = 6
.
in other words, n!
is the product of all integers from 1 to n.
The following code shows the implementation of factorial function:
fact(0) = 1
fact(n) = n * fact(n  1), n > 0
Implementation
The recursive implementation of a function consists of two parts.
 The base case, which gives the value of the function for a specific argument. This is also known as the anchor, end case, or terminating case, and it allows the recursion to terminate eventually.
 The recursive (or general) case where the function is defined in terms of itself.
then the recursive implementation of factorial ìn java will be:
public int factorial(int n) {
if (n <= 1) { // the base condition
return 1;
} else {
return n * factorial(n  1);
}
}
Key Components of a Recursive Algorithm Design
 What is a smaller identical problem(s)?
 Decomposition
 How are the answers to smaller problems combined to form the answer to the larger problem?
 Composition
 Which is the smallest problem that can be solved easily (without further decomposition)?
 Base/stopping case
Implementation Template
General Template
… method(…) {
if ( … ) { // base case
...
} else { // decomposition & composition
...
}
return … ; // if not void method
}
Only One Base Case
… method(…) {
… result = … ; //base case
if ( … ) { // not base case
//decomposition & composition
result = …
}
return result;
}
Example: Fibonacci Numbers
The Nth Fibonacci number is the sum of the previous two Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, …
the recursive definition of Fibonacci Numbers is as follows:
 Recursive Design:
 Decomposition & Composition
 fibonacci(n) = fibonacci(n1) + fibonacci(n2)
 Base case:
 fibonacci(1) = 0
 fibonacci(2) = 1
 Decomposition & Composition
public static int fibonacci(int n) {
int fib;
if (n > 2) {
fib = fibonacci(n1) + fibonacci(n2);
} else if (n == 2) {
fib = 1;
} else {
fib = 0;
}
return fib;
}
Example: Traversing a Tree
Consider the Node class having 3 members data, left child pointer and right child pointer like below:
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
}
}
We can traverse the tree constructed by connecting multiple Node class's object like below, the traversal is called inorder traversal of tree.
public static void inOrderTraversal(Node root) {
if(root != null) {
inOrderTraversal(root.left); // traverse left sub tree
System.out.print(root.data + " "); // traverse current node
inOrderTraversal(root.right); // traverse right sub tree
}
}
Example: Reverse a string
Below is a recursive code to reverse a string
public class Reverse {
public static void main (String args[]) {
String string = "ABCDEFGH";
System.out.println(reverse(string)); //prints dlrow olleh
}
public static String reverse(String s) {
if (s.length() == 1) {
return s;
}
return reverse(s.substring(1)) + s.charAt(0);
}
}
Types of Recursion
Head recursion
In head recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function).
public void head(int n) {
if(n <= 1) {
return;
} else {
head(n1);
}
System.out.println(n);
}
Tail recursion
In tail recursion, it’s the opposite—the processing occurs before the recursive call. Choosing between the two recursive styles may seem arbitrary, but the choice can make all the diﬀerence.
public void tail(int n) {
if(n <= 1) {
return;
} else {
System.out.println(n);
}
return tail(n1);
}
StackOverflowError
If a recursive call goes "too deep", this results in a StackOverflowError. Java allocates a new frame for every method call on its thread's stack. However, the space of each thread's stack is limited. Too many frames on the stack leads to the Stack Overﬂow (SO). for example, consider the simple recursive funtion:
public static void recursion(int depth) {
if (depth > 0) {
recursion(depth1);
}
}
Calling this method with large parameters (e.g. recursion(50000)
probably will result in a stack overﬂow. The exact value depends on the thread stack size, which in turn depends on the thread construction, commandline parameters such as Xss, or the default size for the JVM.
Recursive Versus Iterative Methods
All recursive algorithms/methods can be rewritten without recursion.
 Iterative methods use loops instead of recursion.
 Iterative methods generally run faster and use less memoryless overhead in keeping track of method calls
When Should You Use Recursion?
 When iterative implementation could be more complicated
 When efficiency is less important it might make the code easier to understand
 These are the important issues:
 Algorithm design
 Tradeoff between readability and efficiency
Exercise

Exercise 1:
 Given a number n, print following pattern without using any loop.
 Examples: Input: n = 16 Output: 16, 11, 6, 1, 4, 1, 6, 11, 16
 Examples: Input: n = 10 Output: 10, 5, 0, 5, 10
 Given a number n, print following pattern without using any loop.

Exercise 2:
 Calculate sum of digit of a number using recursion.
 Examples: Input: 12345 Output: 15
 Calculate sum of digit of a number using recursion.

Exercise 3:
 Given a set of characters generate all possible passwords from them.
 Examples: Input: arr[] = {a, b}, len = 2 Output: a b aa ab ba bb
 Given a set of characters generate all possible passwords from them.