Transcript Recursion

Recursion
Dennis Burford
[email protected]
Exercise
• Number of people in a row?
• Start with person on left:
• How many people to the right
– If no-one to the right, say “one”
– Else ask person to the right, add one to this, and
say the answer
Work this out….
Calculate f(3), where:
and
and
f(x) = 2 * f(x-1)
f(0) = 1
x >=0
f(3)
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
2*
f(1)
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
2*
f(1)
2*
f(0)
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
2*
f(1)
2*
f(0)
1
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
2*
f(1)
2*
1
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
f(2)
2*
2
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f(3)
2*
4
8
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f (3) = 8
Write f (x) in Java code
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
f (x) in Java code
public int f( int x )
{
if ( x == 0 )
return 1;
else
return 2 * f (x-1);
}
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
// Base case
// Recursion
Recursion
• f (x) = 2 * f (x-1) is recursive definition of
a function.
• Function defined in terms of itself.
• Solved by repeatedly applying set of rules.
Recursion in Java
• In Java
– Recursion is when a method calls itself.
– Must be a case when it does not call itself (called the
stopping condition or base case)
• Recursion is an alternative to looping.
• As with looping, recursion can cause your
program to loop forever.
What’s wrong?
public int f( int x )
{
if ( x == 0 )
return 1;
else
return 2 * f (x-1);
}
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
// Base case
// Recursion
What about f (-1)?
public int f( int x )
{
if ( x <= 0 )
return 1;
else
return 2 * f (x-1);
}
f (x) = 2 * f (x-1)
f (0) = 1
x >= 0
// Base case
// Recursion
Efficiency of Recursion
• Any recursive function can be converted to an
equivalent iterative method.
• Although recursion is elegant, it can be inefficient,
because there are more calls to methods.
• Iterative methods are more efficient and faster.
f(0) = 1
f(1) = 2
f(2) = 4
f(3) = 8
f(x) = 2 x
f(x) = 2 * f(x-1)
f(0) = 1
x >= 0
Another way to write f(x) in Java
public int f( int x )
{
int total = 1;
for (int i=0; i<x; i++)
total = total * 2;
return total;
}
// Iterative
Rules of Recursion
1. Base cases: always have base case, which is
solved without recursion
2. Making progress: for recursive cases, call must
always make progress towards base case
3. Design Rule: assume all recursive calls work.
Another Example
• Factorials
– 3! = 3*2*1 = 6
– 4! = 4*3*2*1 = 24
– n! = n*(n-1)*….*3*2*1, n >= 0
• Base case
– 0! = 1
Factorials: Recursive
public static int factorialR( int n )
{
if (n <= 1 )
return 1;
else
return (n * factorialR(n-1));
}
Factorials: Iterative
public static int factorialI( int n )
{
int ans = n;
for (int i = n-1; i>0; i--)
ans *= i;
return ans;
}
Example: Reversing a String
• Reverse() takes String and prints reverse
• Reverse(“dennis”) prints out “sinned”
• Base case?
• Progress?
Another Example: Binary Search
• Sorted array of numbers in ascending order:
3, 5, 6, 7, 15, 19, 24, 27, 35, 40, 68, 70, 72, 75, 81, 90
• Find 81(use recursive function).
To Iterate is Human,
To Recurse Divine