Last updated 2/22/07
Recursion: A definition or algorithm that uses itself in the definition or the solution. (see recursion)
Recursion is akin to iteration. Recursion is more powerful. In both cases we always need some mechanism to stop.
Iteration will have a condition that determines continuation or not; recursion will have a condition that determines whether to call [recursively] again or not.
Recursive call: A method call in which the method being called is the same as the one making the call
Direct recursion: Recursion in which a method directly calls itself
Indirect recursion: Recursion in which a chain of two or more method calls returns to the method that originated the chain,
e.g. A calls B, B calls C, and C calls A
A recursive definition has two parts
Recursive algorithm: A solution that is expressed in terms of (a) a base case and (b) smaller instances of itself
At first recursion may seem hard or impossible, maybe magical at best. However, recursion often provides elegant, short algorithmic solutions to many problems in computer science and mathematics.
Examples where recursion is often used
Uses recursive definitions heavily.
Recursive definitions allow a precise and finite method to express what is legal in a language without having to simply give examples. The number of legal strings may be infinite.
Recursion has a natural connection to the induction method of math proofs.
You must be careful when using recursion. Some recursive solutions can be less efficient than iterative solutions. It is also easy to mishandle the base condition to stop.
Example: Definition for odd positive integers
Base: 1 is an odd positive integer
Recursion: If K is an odd positive integer, then K+2 is an odd positive integer
{1} is in the set by the definition base
with K==1, 1+2 = 3, so 3 is in the set {1,3}
with K==3, 3+2 = 5, so 5 is in the set {1,3,5}
and so, 7, 9, 11, etc. are in the set
If a number cannot possibly be generated from this iterative procedure, then it doesn't meet the definition.
Using the generative approach we see how iteration can be used as part of the solution.
Base: 0! = 1
Recursion: n! = (n-1)! * n
4! = 3! * 4
= ( 2! * 3 ) * 4
= ( ( 1! * 2 ) * 3 ) * 4
= ( ( ( 0! * 1 ) * 2 ) * 3 ) * 4
= ( ( ( 1 * 1 ) * 2 ) * 3 ) * 4 = 24
Apply the definition in reverse until you get to the base.
That is, use the definition repeatedly until you're left with a computation.
public static int factorial(int number){
//check for base
if(number==0) return 1;
//apply recursion
return (number * factorial(number-1));
}
System.out.println(factorial(4)); //--> prints 24
Base: 1 and 1 are the first two Fibonacci numbers
Recursion: every Fibonacci number is the sum of the previous two
Generatively:
1 1 1+1=2 1+2=3 2+3=5 3+5=8 5+8=13 8+13=21 etc.
Recursively (return the k-th number in the sequence, i.e., fib(6) == 8)
public static int fib(int k)
{
if (k<=2) return 1;
return fib(k-1) + fib(k-2);
}
Start out low and increase N slowly!
Factorial and Fibinacci number generation by recursion are examples of inefficiency. Iterative solutions are best in these cases
public static int factorial(int number){
int fact = 1;
for(int i=1; i<=number; i++)
fact *= i;
return fact;
}
public static int fib(int k){
int last = 1;
int nextlast = 1;
if (k <= 2) return last;
for(int i=3; i<=k; i++){
int sum = last+nextlast;
nextlast = last;
last = sum;
}
return sum;
}
See how big you can go with this non-recursive implementation
1! = F[1] = 1
2! = F[2] = 2
3! = F[3] = 6
4! = F[4] = 24
The Base-Case Question: Is there a nonrecursive way out of the method, and does the method work correctly for this base case?
The Smaller-Caller Question: Does each recursive call to the method involve a smaller case of the individual problem, leading inescapably to the base case?
The General-Case Question: If the recursive call(s) works correctly, does the whole method work correctly?
Induction!
Constraints often exist on the valid input arguments for a recursive algorithm. For example, for Factorial, n must be >= 0.
This is the "meta"-language to express the syntax of a programming language.
BNF consists of a series of productions or rewrite rules. Some productions are base oriented and refer to fixed strings; some productions make references to other production which can be recursive. The following example defines the legal syntax of a monetary constant "a '$' followed by one or more digits optionally followed by a decimal point followed by two decimals"
money ::= $ value
value ::= dollars | dollars '.' cents
dollars ::= DIGIT | ( DIGIT dollars )
cents ::= DIGIT DIGIT
DIGIT := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
is usedStart with the "start symbol", usually the left side non-terminal of the first production. Substitute a right hand side of a production. Repeat until you match the syntactic input.
Example
Is "$2.05" a money string?
'$' '2' '.' '0' '5' are the tokens to be matched to the terminals as our goal
money
=> $ dollar . cents
=> $ DIGIT . cents
=> $ 2 . cents
=> $ 2 . DIGIT DIGIT
=> $ 2 . 0 DIGIT
=> $ 2 . 0 5
expr := term
| expr addingOp term
term := factor
| term multOp factor
factor := number
| '(' expr ')'
addingOp := '+' | '-'
multOp := '*' | '/' | '%'
number := digit | number digit
digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Consider the string "(12 + 4) * 3". Is it legal?
An example of a recursive structure and recursive processing
MelSmith BevOlsen
|_________|
|
BenJones AdaWhite JimSmith NanBlack
|________| |____________|
_____|_______ __________|_
| | | |
JoeJones SamJones SueSmith KaySmith TimHowe
|_______________| |____________|
_____________|___________ |
| | | |
IraJones AnnJones MiaJones BobHowe
|
|
public static int Ancs(Relative inx)
{
if(inx==Unknown){
return 0;
} else {
return Ancs(father[inx])
+ Ancs(mother[inx]) + 1;
}
}