Recursion
Objective #1: Trace recursive methods.
- A recursive method is a method that calls itself until some specified condition has been satisfied. Recursion is the process in which a method calls itself repeatedly until some specified condition has been satisfied.
- Java, C++, C, and most other "powerful" languages support recursion but some do not (notably old-fashioned versions of BASIC).
- You should be able to trace easy mathematical recursive method such as the following example where ^ is used to denote exponentiation.
f(x) = f(x+1) + x if x < 5
x^2 otherwise
f(2) = f(2+1) + 2 = f(3) + 2 = f(3+1) + 3 + 2 = f(4) + 3 + 2 = f(4+1) + 4 + 3 + 2 = f(5) + 4 + 3 + 2 = 5 ^ 2 + 4 + 3 + 2 = 34
- The following program recursively computes the f(2)
public class RecursionDemo
{
public static void main(String[] args)
{
System.out.println(f(2));
}
public static int f(int x)
{
if (x < 5)
return f(x + 1) + x;
else
return x * x;
}
}
- See this handout which is an illustration of how I trace the recursive method above.
- The information below is not really tested on the Computer Science AP Exam. But it is useful to read anyway.
- Here's an interesting demo program that converts a decimal number into its equivalent binary number using a recursive method:
public class RecursionDemo
{
public static void main(String[] args)
{
System.out.println(convertToBinary(10));
}
private static String convertToBinary(int n)
{
if (n == 0)
{
return "";
}
return cvtBinary(n / 2) + (n % 2);
}
}
- If you've studied mathematical induction in math class, you'll see that it relates to recursive programming.
- The simplest kind of recursive method includes a base case and just one recursive case. This type of method typically results in a series of pushes to the call stack and then a series of pops from the call stack.
- More complicated recursive methods however include a base case and two or more recursive method calls. This type of method results in some pushes followed by a few pops but then more pushes and then a few pops until the stack grows to its largest size and then the reverse sequence with more pops than pushes.
- A recursive method is tail recursive if the recursive call is the very last statement in the method. Since local variables no longer need to be kept in the stack frame, efficient compilers translate tail recursive code into maching language that simply uses iterative code. In this case, the compiler treats method parameters as variables associated with the loop and no stack is required.
- Somtimes an error is made when writing a recursive method and infinite recursion results. Infinite recursion, like infinite loops, is almost never desirable. The computer will eventually crash with a stack fault or stack overflow error message (i.e. java.lang.StackOverflowError ...). Infinite recursion is often the result when the programmer forgot to decrement a parameter.
- Good lesson with quizzes and programming exercises - chortle.ccsu.edu/CS151/cs151java.html#70
- Good lesson with practice multiple choice exercises - www.cs.washington.edu/apcs/lessons/recursion
- See this set of animations which illustrate recursion
Objective #2: Explain the relationship between recursion and iteration.
- Often recursive solutions can be translated into iterative ones and vice versa. As was mentioned above, an efficient compiler sometimes converts source code that is written with recursion into machine code that uses iteration. For example, both of these methods produce the same output. The one works recursively and the other works iteratively:
// iterative method (i.e. a method that uses a regular loop) ************
public static int addEmUp(int num)
{
int sum = 0;
for (int i = 0; i <= num; i++)
{
sum += i;
}
return sum;
}
// recursive method ******************************************************
public static int addEmUp(int num)
{
if (num == 1)
{
return 1;
}
return num + addEmUp(num - 1);
}
- Usually an iterative version of a solution executes more quickly than a recursive one. Sometimes, iterative solutions are much faster and more memory efficient than recursive ones.
- However, recursive solutions are often easier to write than iterative ones.
Objective #3: Write recursive methods.
- This is no longer required on the AP Computer Science Exam.
- A recursive method usually includes a base case and one or more recursive cases. The base case causes the method to end and, without it, infinite recursion or stack fault would occur. The recursive case moves the algorithm toward the base case and eventual termination. A recursive method is usually implemented as an if, if else, or if else if else statement.
- Here is the general form for a recursive method:
public void recursiveMethod(...)
{
if (base case, possibly n==0)
{
// perform some action
}
else
{
// perform some other action
recursiveMethod(...n - 1..);
// possibly perform anaction, but the method will not be tail recursive
}
}
- When you write recursive functions it is sometimes difficult
to identify the proper base case that you need to use.
- Using a helper method sometimes makes it simpler to solve a recursive problem. The
non-recursive helper method makes a slight change to the original problem
which then makes it easier to write another method that is recursive.
Objective #4: Identify the efficient and the inefficient
use of recursion.
- This is no longer required on the AP Computer Science Exam.
- Recursion should mainly be used to simplify your code without too much loss of performance. Recursion can be used rather efficiently with nested data structures or branching processes. For example, traversing binary trees is a good application for recursion. However, with linear structures such as arrays, you might as well use iteration rather than recursion.
- Do not use recursion when:
- a method contains large local arrays since this will cause large stack frames that eventually may cause stack overflow
- a method manipulates any global variables
- the same method could be implemented with plain loop iteration and result in faster performance (e.g. factorial, Fibonacci, linear search)
- Do use recursion when:
- it significantly simplifies code
- a divide-and-conquer algorithm is suitable (e.g. mergesort, quicksort)
- Try implementing the following algorithms with recursion rather than iteration and decide which ones are much more inefficient with the recursive solution:
- reversing the digits of a positive integer
- reversing the characters of a string
- detecting palindromes
- finding a greatest common divisor
- finding the sum of two integers (digit by digit)
- multiplying two integers (digit by digit)
- computing a number to a power
- computing the Fibonacci sequence
- computing a factorial
- finding the sum of the elements of an array
- print the elements of an array backwards
- a linear search
- a binary search
- a selection sort
- an insertion sort
- a merge sort
- a quicksort
- generating all of the possible permutations of a given set of characters
- N Choose K (combinatorics)
- printing the nodes of a linked list
- printing the nodes of a linked list in reverse order
- Towers of Hanoi
- Eight Queen