Recursion
 Contents
 Introduction to Recursion
 Solving Problems with Recursion
 Direct and Indirect Recursion
 Summing a Range of Array Elements
 Palindromes
 The Fibonacci Series
 Greatest Common Divisor
 Recursive Binary Search
 The Towers of Hanoi
 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:
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:
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
ton
. 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 numbern
.The factorial of a nonnegative 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
is0
, its factorial is1
.When
n
is greater than0
, its factorial is the product of all positive integers from1
up ton
.
factorial(6)
is calculated as:1 × 2 × 3 × 4 × 5 × 6 = 720.
The base case is the condition in which
n
equals0
: If
n = 0
Thenfactorial(n) = 1
 If
The recursive case, or the part of the problem that use recursion to solve is:
 if
n > 0
thenfactorial(n) = n × factorial(n  1)
 if
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:
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 methodB
, which in turn calls methodA
.There can even be several methods involved in the recursion.
For example, method
A
could call methodB
, which could call methodC
, which could call methodA
.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
 an
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")
returnstrue
palindrome("series")
returnsfalse
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 wellknown 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
and1
, 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:
Rabbits are able to mate at the age of one month, so at the end of her second month a female can produce babies.
Rabbits mate every month.
Rabbits produce one new pair, one male and one female, every time they mate.
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 nonzero integers, is the largest positive integer that divides the numbers without a remainder.
For example, looking for the GCD of
54
and24
: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
and24
:1, 2, 3, 6
The GCD of
54
and24
is6
.
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 halfinterval 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
, andC
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 pegC
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 pegA
to pegC
using pegB
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 pegA
to pegC
.If
n > 1
Then:Move
n  1
discs from pegA
to pegB
using pegC
as a temporary peg.Move the remaining disc from peg
A
to pegC
.Move the
n  1
discs from pegB
to pegC
using pegA
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.^{1}

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 bottomcenter 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.
Click on the Applet, and drag your mouse up and down to view changes in the binary fractal tree.