Recursion

1. Contents
2. Introduction to Recursion
3. Solving Problems with Recursion
4. Direct and Indirect Recursion
5. Summing a Range of Array Elements
6. Palindromes
7. The Fibonacci Series
8. Greatest Common Divisor
9. Recursive Binary Search
10. The Towers of Hanoi
11. Binary Fractal Tree

Introduction to Recursion

• We have been calling other methods from a method.

• It’s also possible for a method to call itself.

• A method that calls itself is a recursive method.

• Book example:

  • EndlessRecursion.java

• Example code:

  public class Program {
  	public static void main(final String[] args) {
  		printRecursive();
  	}
  
  	private static void printRecursive() {
  		System.out.println("This is a recursive method.");
  		printRecursive();
  	}
  }

• The method in the example displays the string “This is a recursive method.”, and then it calls itself.

• Each time the method calls itself, the cycle is repeated endlessly.

• Like a loop, a recursive method must have some way to control the number of times it repeats.

• Example:

  • Recursive.java
  • RecursionDemo.java

• Example code:

  public class Program {
  	public static void main(final String[] args) {
  		printRecursive(10);
  	}
  
  	private static void printRecursive(final int n) {
  		if (n == 0)
  			return;
  		System.out.println(n);
  		printRecursive(n - 1);
  	}
  }

Solving Problems with Recursion

• Recursion can be a powerful tool for solving repetitive problems.

• Recursion is never absolutely required to solve a problem.

• Any problem that can be solved recursively can also be solved iteratively, with a loop.

  Example: the sum of natural numbers from 1 to n. We first solve it iteratively.

  public class Program {
  	public static void main(final String[] args) {
  		final int n = 10;
  		System.out.println("sum = " + sum(n));
  	}
  
  	private static int sum(final int n) {
  		int sum = 0;
  		for (int i = 1; i <= n; i++)
  			sum += i;
  		return sum;
  	}
  }

  We can also solve it recursively.

  public class Program {
  	public static void main(final String[] args) {
  		final int n = 10;
  		System.out.println("sum = " + sum(n));
  	}
  
  	private static int sum(final int n) {
  		if (n <= 0)
  			return 0;
  		return n + sum(n - 1);
  	}
  }

• In many cases, recursive algorithms are less efficient than iterative algorithms.

• Recursive solutions repetitively:
  

  • Allocate memory for parameters and local variables.
  • Store the address of where control returns after the method terminates.

• These actions are called overhead and take place with each method call.

• This overhead does not occur with a loop.

• Some repetitive problems are more easily solved with recursion than iteration.
  

  • Iterative algorithms might execute slightlt faster.
  • A recursive algorithm might simpler to design, implement, debug, test, and analyze.

• Recursion works like this:

  • If a simple base case is matched,
    the method returns the simple result.

  • If the simple base case is not matched,
    the method reduces the input to a smaller problem (the recursive case) and calls itself to solve the smaller problem.

• By reducing the problem with each recursive call, execution will eventually reach the base case and the recursion will stop.

• Example Problem Solving

  • In mathematics, the notation n! represents the factorial of the number n.

  • The factorial of a non-negative number can be defined by the following rules:

    • If n = 0 Then n! = 1
    • If n > 0 Then n! = 1 × 2 × 3 × ... × n

  • These rules state that:

    • When n is 0, its factorial is 1.

    • When n is greater than 0, its factorial is the product of all positive integers from 1 up to n.

  • factorial(6) is calculated as:

    • 1 × 2 × 3 × 4 × 5 × 6 = 720.

  • The base case is the condition in which n equals 0:

    • If n = 0 Then factorial(n) = 1

  • The recursive case, or the part of the problem that use recursion to solve is:

    • if n > 0 then factorial(n) = n × factorial(n - 1)

  • The recursive call works on a reduced version of the problem, n - 1.

  • The recursive rule for calculating the factorial:

    • factorial(n) = 1, n = 0
    • factorial(n) = n × factorial(n - 1), n > 0

  • Example:

    • FactorialDemo.java

  • Example code:

    public class Program {
    	public static void main(final String[] args) {
    		final int n = 4;
    		System.out.println(n + "! = " + factorial(n));
    	}
    
    	private static int factorial(final int n) {
    		if (n == 0)
    			return 1;
    		return n * factorial(n - 1);
    	}
    }

  • Track recursive calls

    

Direct and Indirect Recursion

• When recursive methods directly call themselves it is known as direct recursion.

• Indirect recursion is when method A calls method B, which in turn calls method A.

• There can even be several methods involved in the recursion.

• For example, method A could call method B, which could call method C, which could call method A.

• Care must be used in indirect recursion to ensure that the proper base cases and return values are handled.

Summing a Range of Array Elements

• Recursion can be used to sum a range of array elements.

• A method rangeSum takes following arguments:

  • an int array
  • an int specifying the starting element of the range
  • an int specifying the ending element of the range

• It might be called like:

  int[] nums = { 1, 23, 21, 3, 5, 56, 2, 6, 4 };
  int sum = rangeSum(nums, 3, 5);

• The sum is taken inclusively regarding both indexes. The example above would result in:

  • sum = 3 + 5 + 56 = 64
• A recursive Java solution:

  public class Program {
  	public static void main(final String[] args) {
  		final int[] nums = { 1, 23, 21, 3, 5, 56, 2, 6, 4 };
  		System.out.println("rangeSum = " + rangeSum(nums, 3, 5));
  	}
  
  	private static int rangeSum(
  			final int[] nums,
  			final int start,
  			final int end) {
  
  		if (start > end)
  			return 0;
  
  		return nums[start] + rangeSum(nums, start + 1, end);
  	}
  }

Palindromes

• Consider a simple problem of determining whether or not a String is a palindrome. A palindrome is a string that reads the same forwards and backwards.

  • bob
  • mom
  • dad
  • noon
  • level

• We need to be able to express the palindrome problem in terms of smaller palindrome problems.

• The recursive relation: A string is a palindrome if its first and last characters are identical, and the inner substring is a palindrome.

• The problem is reduced to a smaller problem of the same kind.

• An illustration demonstrating a good case and a bad case.

  

• The method is going to be called like this:

  • palindrome("level") returns true
  • palindrome("series") returns false

• Consider the base case, or cases.

  • If a string is empty, return true; i.e., an empty string is considered a palindrome.

  • If the string contains only one character, return true.

• A recursive Java solution:

  public class Program {
  	public static void main(final String[] args) {
  		final String str = "level";
  		System.out.println("Q: is '" + str + "' a palindrome?");
  		System.out.println("A: " + palindrome(str));
  	}
  
  	private static boolean palindrome(final String str) {
  		final int len = str.length();
  		if (len == 0 || len == 1) // or len <= 1
  			return true;
  
  		if (str.charAt(0) != str.charAt(len - 1))
  			return false;
  
  		return palindrome(str.substring(1, len - 1));
  	}
  }

The Fibonacci Series

• Some mathematical problems are designed to be solved recursively. One well-known example is the calculation of Fibonacci numbers.

• In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:

  • 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

• By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

• In mathematical terms, the sequence F(n) of Fibonacci number is defined by the following recurrence relation:

  • f(0) = 0
  • f(1) = 1
  • f(n) = f(n - 1) + f(n - 2) : n > 1

• A little history of Fibonacci numbers: the rabbit puzzle proposed by Fibonacci.

  In the West, the Fibonacci sequence first written by Leonardo of Pisa, known as Fibonacci. Fibonacci considers the growth of an idealized rabbit population, assuming that:

  1. Rabbits are able to mate at the age of one month, so at the end of her second month a female can produce babies.

  2. Rabbits mate every month.

  3. Rabbits produce one new pair, one male and one female, every time they mate.

  4. Rabbits never die.

  Question: A newly born pair of rabbits, one male and one female, are put in a field; how many pairs will there be in one year?

  Month one:	1 pair
  Month two:	2 pair
  Month three:	3 pair
  Month four:	5 pair
  Month five:	8 pair
  Month six:	12 pair

• A recursive Java solution

  public class Program {
  	public static void main(final String[] args) {
  		final int n = 12;
  		System.out.println("fibonacci(" + n + ") = " + fibonacci(n));
  	}
  
  	private static int fibonacci(final int n) {
  		if (n == 0)
  			return 0;
  
  		if (n == 1)
  			return 1;
  
  		return fibonacci(n - 1) + fibonacci(n - 2);
  	}
  }

Greatest Common Divisor (GCD)

• In mathematics, the greatest common divisor (GCD), also known as the greatest common factor (GCF), or highest common factor (HCF), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

• For example, looking for the GCD of 54 and 24:

  • Divisors of 54: 1, 2, 3, 6, 9, 18, 27, 54

  • Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24

  • Common divisors of 54 and 24: 1, 2, 3, 6

  • The GCD of 54 and 24 is 6.

• A recursive Java solution

  public class Program {
  	public static void main(final String[] args) {
  		final int m = 54;
  		final int n = 24;
  		System.out.println("GCD(" + m + ", " + n + ") = " + gcd(m, n));
  	}
  
  	private static int gcd(final int x, final int y) {
  		if (y == 0)
  			return x;
  
  		if (x % y == 0)
  			return y;
  
  		return gcd(y, x % y);
  	}
  }

Recursive Binary Search

• In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array.

• The binary search algorithm can be implemented recursively.

• The procedure can be expressed as:

  • If the middle element of the input array equals the search value, then the value is found.

  • Otherwise if the middle element of the input array is less than the search value, perform a binary search on the upper half of the array.

  • Otherwise if the middle element of the input array is greater than the search value, perform a binary search on the lower half of the array.

• A recursive Java solution

  public class Program {
  	public static void main(final String[] args) {
  		final int[] array = { 2, 3, 4, 5, 12, 21, 23, 34, 36, 47, 56 };
  		final int n = 34;
  		System.out.println("index of " + n + ": " + binarySearch(array, n));
  	}
  
  	private static int binarySearch(final int[] array, final int key) {
  		return binarySearch(array, key, 0, array.length - 1);
  	}
  
  	private static int binarySearch(
  			final int[] array,
  			final int key,
  			final int start,
  			final int end) {
  
  		if (start > end)
  			return -1;
  
  		final int middle = (start + end) / 2;
  
  		if (array[middle] == key)
  			return middle;
  
  		if (array[middle] < key)
  			return binarySearch(array, key, middle + 1, end);
  
  		return binarySearch(array, key, start, middle - 1);
  	}
  }

The Towers of Hanoi

• The Towers of Hanoi is a mathematical game that uses:

  • Three pegs, A, B, and C

  • A set of n discs with holes through their centers

• The discs are stacked on peg A in order of size with the largest disc at the bottom.

• The object of the game is to move the discs from peg A to some peg C while observing the following rules:

  • Only one disc may be moved at a time.

  • A disc cannot be placed on top of a smaller disc.

  • All discs must be on pegs except the one disc being moved.

• The overall solution to the problem is to move n discs from peg A to peg C using peg B as a temporary peg.

• The diagram below demonstrates the steps for solving a Towers of Hanoi game with three discs.

  

• This algorithm solves this game.

  • If n = 1 Then: move the disc from peg A to peg C.

  • If n > 1 Then:

    • Move n - 1 discs from peg A to peg B using peg C as a temporary peg.

    • Move the remaining disc from peg A to peg C.

    • Move the n - 1 discs from peg B to peg C using peg A as a temporary peg.

  We notice the base case also be when n = 0. There's simply nothing to be done in this case.

• A recursive Java solution

  public class Program {
  	public static void main(final String[] args) {
  		solveTowersOfHanoi(4, 'A', 'C', 'B');
  	}
  
  	private static void solveTowersOfHanoi(
  			final int n,
  			final char srcPeg,
  			final char dstPeg,
  			final char tmpPeg) {
  
  		if (n == 1)
  			return;
  
  		solveTowersOfHanoi(
  				n - 1,
  				srcPeg,
  				tmpPeg,
  				dstPeg);
  
  		System.out.println(""
  				+ "Move a disc from "
  				+ srcPeg
  				+ " to "
  				+ dstPeg);
  
  		solveTowersOfHanoi(
  				n - 1,
  				tmpPeg,
  				dstPeg,
  				srcPeg);
  	}
  }

Binary Fractal Tree

Recursion can help in displaying complex patterns where the pattern appears inside itself as a smaller version. Such patterns, called fractals, are in fact a visual manifestation of the concept of recursion.¹

• import java.awt.Color;
  import java.awt.Dimension;
  import java.awt.Graphics;
  import java.awt.Graphics2D;
  import java.awt.event.MouseEvent;
  import java.awt.event.MouseMotionAdapter;
  import java.awt.geom.Line2D;
  import java.awt.geom.Point2D;
  
  import javax.swing.JFrame;
  import javax.swing.JPanel;
  import javax.swing.WindowConstants;
  
  public class Program {
      public static void main(final String[] args) {
  
          // Create the component that will draw the tree.
          final FractalTree tree = new FractalTree();
          tree.setPreferredSize(new Dimension(500, 500));
  
          // Create the panel that hosts the tree component,
          // and show it centered on the screen.
          final JFrame frame = new JFrame("Tree Recursion");
          frame.setContentPane(tree);
          frame.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
          frame.pack();
          frame.setLocationRelativeTo(null);
          frame.setVisible(true);
      }
  }
  
  class FractalTree extends JPanel {
  	private static final long serialVersionUID = 0L;
  
  	double angleDelta = Math.toRadians(20.0);
  
  	FractalTree() {
  		this.setBackground(Color.BLACK);
  
  		this.addMouseMotionListener(new MouseMotionAdapter() {
  			@Override
  			public void mouseDragged(final MouseEvent e) {
  				// When the mouse is dragged, adjust the angle
  				// adjustment factor, and repaint this component.
  				final FractalTree tree = FractalTree.this;
  				tree.angleDelta = Math.toRadians(
  						(e.getY() * 180.0) / tree.getHeight());
  				tree.repaint();
  			}
  		});
  	}
  
  	private void paintBranch(
  			final Graphics2D g,
  			final Point2D p1,
  			final double length,
  			final double angle) {
  
  		// End case: Do not draw branches smaller than this length.
  		if (length < 4.0)
  			return;
  
  		// Determine the other end of the line segment based on
  		// the specified point, the length of the branch, and
  		// the branch angle.
  		final Point2D p2 = new Point2D.Double(
  				p1.getX() + (length * Math.cos(angle)),
  				p1.getY() + (length * Math.sin(angle)));
  
  		// Draw the branch.
  		g.draw(new Line2D.Double(p1, p2));
  
  		// Recursively draw two neighboring branches.
  		this.paintBranch(g, p2, 0.75 * length, angle - this.angleDelta);
  		this.paintBranch(g, p2, 0.75 * length, angle + this.angleDelta);
  	}
  
  	@Override
  	protected void paintComponent(final Graphics g) {
  		super.paintComponent(g);
  
  		// Set the color of the branch lines.
  		final Graphics2D g2d = (Graphics2D)g;
  		g2d.setColor(new Color(200, 54, 0));
  
  		// Get the size of this component.
  		final Dimension size = this.getSize();
  
  		// Determine the starting point for the trunk of the tree,
  		// which is at the bottom-center position in this component.
  		final Point2D.Double p0 = new Point2D.Double(
  				0.50 * size.width,
  				0.85 * size.height);
  
  		// Determine an initial length for the branches.
  		final double length0 = 0.20 * size.height;
  
  		// Initially, paint the trunk upward into the component.
  		final double angle0 = Math.toRadians(270.0);
  
  		// Recursively paint the tree.
  		this.paintBranch(g2d, p0, length0, angle0);
  	}
  }

  If your browser supports Applets, you can view a version of this program below, formatted for this website.

  Your browser does not support Applets.

  Click on the Applet, and drag your mouse up and down to view changes in the binary fractal tree.