Recursion Examples
originally by Nicholas Ruozzi and Lisa Minich (2005)
enhanced/fixed by Andrew Tibbits, Changxi Zheng, David Schwartz (2006)
Here's a mathematical view of Recursion:
We want to take the kth state and reduce it to the (k-1)th state.
When does k stop? The "base case" (i.e., stopping point) of a recursive
problem.
A problem that involves a repeated solution can be thought of
as iterative:
example) iterative sum of numbers 0 through k:
int sum =0;
for(int i=1; i<=k; i++) { // stop when max # reached
sum += i; // increment sum
}
or recursive:
example) recursive sum of numbers
public int sum(int n) {
if(n==0) // base case
return 0;
else // recursive case
return sum(n-1) + n;
}
The nth state is added to the (n-1) th state for all n greater
than the base case, which is 0 in this example.
When should you use iteration or recursion?
- Development process: which is clearer? more intuitive?
(often recursion)
- Runtime performance: which involves less memory? faster processing?
(often iteration)
These questions will be easier to address as you learn more about data
structures and algorithm analysis.
Tail Recursion:
A method is tail recursive if the last action of the recursive method
is the recursive call. In the examples below, the solutions to Problems
1 and 2 are not tail recursive, but the solution to Problem 3 is tail
recursive. Because recursion builds frame upon frame of the stack, the
additional overhead required by non-tail recursive functions could be
costly for large inputs.
example) Problem 1, Reverse a string recursively:
/* From the API: String substring(int beginIndex, int endIndex)
* Returns a new string that is a substring of this string.
* The substring begins at the specified beginIndex and extends
* to the character at index endIndex - 1.
*/
public String reverseString(String word) {
if(word == null || word.equals(""))
return word;
else
return reverseString(word.substring(1, word.length())) +
word.substring(0,1);
}
example) Problem 2, Remove consecutive duplicates from a string recursively.
For example, convert "aabccba" to "abcba":
public String removeDuplicates(String word) {
if(word == null || word.length() <= 1)
return word;
else if( word.charAt(0) == word.charAt(1) )
return removeDuplicates(word.substring(1, word.length()));
else
return word.charAt(0) +
removeDuplicates(word.substring(1, word.length()));
}
example) Problem 3 (Compute n mod m without using %):
Note: Divisor cannot be zero, otherwise in this code it would
be called recursively forever. Also,we may consider the case
that either val or divisor are negative. In this case, it is
possible for this code to lead a stack overflow (i.e., the call
stack runs out of memory).
public int modulus(int val, int divisor) {
if(val < divisor)
return val;
else
return modulus(val - divisor, divisor);
}
Suggested improvement:
public int modulus(int val, int divisor) {
if ( divisor==0 ) return 0; // check for prevent from stack overflow.
// It's better to raise an ArithmeticException
// in this case.
boolean neg = val < 0;
val = Math.abs(val);
divisor = Math.abs(divisor);
if (val < divisor)
return neg ? -val : val;
else
return neg ? -modulus(val - divisor, divisor):
modulus(val - divisor, divisor);
}
Is it possible to convert non-tail recursive functions into tail
recursive ones? The answer is usually yes. To illustrate the
process, we've redone Problem 1 using tail recursion and a helper
method. Below, reverseString is a 'hook,' which starts the actual
recursive calls with an initial value (sometimes the hook will pass
additional information):
example) Poblem 4 -- redo Problem 1 with Tail Recursion:
// Reverse a string (this is the hook):
public String reverseString(String word) {
return tailReverse(word, ""); // now call the recursion; the ""
// helps to store the reversed letters
}
// Reverse letters in word, removing them from left to right one at
// a time and adding from right to left in res:
public String tailReverse(String word, String res) {
if(word==null || word.equals("")) // null is no String; "" is empty String
return res;
else
return tailReverse(word.substring(1, word.length()),
word.charAt(0) + res);
}
Suppose word is null, it is more reasonable to return null rather than an empty
string. So the code above should change a little as follows:
// Reverse a string (this is the hook):
public String reverseString(String word) {
if ( word == null ) return word;
return tailReverse(word, ""); // now call the recursion; the ""
// helps to store the reversed letters
}
// Reverse letters in word, removing them from left to right one at
// a time and adding from right to left in res:
public String tailReverse(String word, String res) {
if( word.equals("") ) // null is no String; "" is empty String
return res;
else
return tailReverse(word.substring(1, word.length()),
word.charAt(0) + res);
}
Some more examples:
example) What is the result of mystery (2, 25)? mystery(3, 35)?
Given positive integers a and b, describe what mystery(a, b) does.
mystery(2,25) = 50
mystery(3,35) = 105
mystery(a,b): multiplies a and b
public int mystery(int a, int b) {
if (b == 0)
return 0;
else if (b % 2 == 0)
return mystery(a + a, b / 2);
else
return mystery(a + a, b / 2) + a;
}
example) Find the gcd (greatest common divisor) of 2 numbers:
public int gcd(int a, int b) {
int remainder = a % b;
if (remainder == 0)
return b;
else
return gcd(b, remainder);
}
example) Write print out the binary representation of a given number:
Note that the binary representation of 0 should be 0.
public void convertBinary( int n ) {
if( n<2 ) {
System.out.println(n);
return;
}
convertBinary(n/2);
System.out.println(n % 2);
}
example) What is f(0)?
f(0) = 997
public static int f(int x) {
if( x > 1000)
return x-4;
else
return f(f(x+5));
}
example) Merge two strings that are ordered alphabetically.
The result should also be alphabetical.
public String merge(String first, String second) {
if(first ==null || first.equals(""))
return second==null? first:second;
else if (second == null || second.equals(""))
return first;
else if(first.charAt(0) < second.charAt(0))
return first.charAt(0) + merge( first.substring(1, first.length()), second);
else
return second.charAt(0) + merge(first, second.substring(1, second.length()));
}
example) Given an array of characters and the length of the array, print out
all the permutations of the array. Hint: you might need a helper method.
Our solution fixes the last element of the array instead of the first. You could
also fix the first letter.
public void permute(char[] a, int length) {
if (length == 1) {
System.out.println(a);
return;
}
for (int i = 0; i < length; i++) {
swap(a, i, length-1);
permute(a, length-1);
swap(a, i, length-1);
}
}
public void swap(char[] a, int i, int j) {
char c;
c = a[i];
a[i] = a[j];
a[j] = c;
}