|
Topics
- Simple recursion
- Recursion with a return value.
- Binary search revisited.
- Recursion versus Iteration.
- Big problem reduce to a simple case or base
case.
Factorial example
5! = 5 * 4 * 3 * 2 * 1
4! = 4 * 3 * 2 * 1
3! = 3 * 2 * 1
2! = 2 * 1
1! = 1 this is base case
5! 120
5! = 5 * 4! 24
5! = 5 * 4 * 3! 6
5! = 5 * 4 * 3 * 2! 2
5! = 5 * 4 * 3 * 2 *1! 1
A for loop will solve this problem. We can also
solve this recursively. You reduce the size of the problem each time you
solve for a factorial. The reduction is the general case? The reduced is
the base case. .
Java Text Books
Recursive methods
- Method that invokes itself.
- The arguments passed to the recursion take us
closer to the solution with each call.
Coding the recursive Method.
- Factorial
n! = n * (n-1)!
* (n-1) * (n-2)!
*
public class RecursiveFactorial
{
public static void main( String [] args )
{
// compute factorial of 7 and output it
System.out.println( "Factorial ( 7 ) is "
+ factorial( 7 ) );
}
public static int factorial( int n )
{
if ( n <= 0 ) // base case
return 1;
else // general case
return ( n * factorial ( n - 1 ) );
}
}
- Start handling the base case first, example
uses 0 not 1 which is more mathematically correct. Compiler hangs on to
the value of the method but because it can't solve it, it starts building a
stack and tries to solve it by continuing to call itself and keeps a record
in memory called an activation record
1*fact(0) this returns 1 as above and now stack
executes the returns
2*fact(1) this returns 2
3*fact(2) this returns 6
4*fact(3) this returns 24
5*fact(4) this returns 120
This generates a lot of memory, more than the
for loop. Some argues that recursion is more readable.
Recursive binary search code
- Take four parameters, array reference, key,
beginning and end.
Recursion versus iteration
- Efficiency is slower.
- Readability and maintenance is supposed to be
better.
|
