Recursion

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 non-negative 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 is 3×2!. * Since 2 > 0, 2! is 2×1!, and 3! becomes 3×2×1!. * Since1 > 0,1!is1×0!, and3!becomes3×2×1×0!* Since0!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(n-1) + fibonacci(n-2)
  • Base case:
    • fibonacci(1) = 0
    • fibonacci(2) = 1

public static int fibonacci(int n) {
  int fib;
  if (n > 2) {
    fib = fibonacci(n-1) + fibonacci(n-2);
  } 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 in-order 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(n-1);
  }
  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 difference.

public void tail(int n) {   
  if(n <= 1) {
    return;    
  } else {
    System.out.println(n);
  }
  return tail(n-1);
}  

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 Overflow (SO). for example, consider the simple recursive funtion:

public static void recursion(int depth) {
  if (depth > 0) {
    recursion(depth-1);
  }
}

Calling this method with large parameters (e.g. recursion(50000) probably will result in a stack overflow. The exact value depends on the thread stack size, which in turn depends on the thread construction, command-line 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 memory--less 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

• Exercise 2:

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

• 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