Transcript Recursion

Recursion
• A method of defining a concept which refers
to the concept itself
• A method of solving a problem by reducing
it to smaller versions of itself
• A powerful, elegant, efficient way to solve
certain classes of programming problems
• A recursive function calls itself
4/9/2016
cosc237/recursion
1
Recursive definitions
Relative: x is a relative of y iff (if and only
•
•
•
•
if)
x is
x is
x is
x is
4/9/2016
y’s parent
y’s child
y’s spouse
a relative of a relative of y
cosc237/recursion
2
Recursive definitions cont’d
Natural numbers
• 1 is a natural number
• if i is an natural number, then i+1 is a
natural number
• Definition in which a problem is
expressed in terms of a smaller version
of itself
• Has one or more base cases
4/9/2016
cosc237/recursion
3
Example 1:
void message() //infinite recursive function
{
System.out.println("This is a recursive function.)";
message();
}
4/9/2016
cosc237/recursion
4
Example 2:
void message(int times)
{
if (times > 0)
{
System.out.println("This is a recursive function.)";
message(times -1);
}
}
4/9/2016
cosc237/recursion
5
message (4);
//Each call creates an activation record or frame.
1st call
times: 4
2nd call
times: 3
3rd call
times: 2
4/9/2016
cosc237/recursion
4th call
times: 1
5th call
times: 0
6
Recursion requires
1. base case
2. general case
4/9/2016
cosc237/recursion
7
General format for
Many Recursive Functions
if (some easily-solved condition) // base case
solution statement
else
// general case
recursive function call
8
• Base part
– states one or more cases that satisfy the
definition
– No base->infinite recursion
• recursive part
– states how to apply the definition to satisfy
other cases
– with repeated applications, reduces to base
• implicitly: nothing else satisfies the
definition
4/9/2016
cosc237/recursion
9
Example #3:
• Find the sum of all int numbers
between 1 and n.
• Sum(5) = 1 + 2 + 3 + 4 + 5 = 15
• Base case: Sum (1) = 1
• General Case:
Sum (2) = 1 + 2
= Sum(1) + 2
= Sum (n-1) + n
4/9/2016
cosc237/recursion
10
Finding the Sum of the Numbers
from 1 to n
int Summation ( int n )
{
if ( n == 1)
return 1 ;
else
// base case
// general case
return ( n + Summation ( n - 1 ) ) ;
}
1111
Exercises
• Write a function using recursion to
print numbers from n to 0.
• Write a function using recursion to print
numbers from 0 to n. (You just need to
shift one line in the program above)
4/9/2016
cosc237/recursion
12
Solution:
//n to 0
void Print(int n)
{
System.out.println(n );
if (n <= 0)
return;
Print(n-1);
}
4/9/2016
//0 to n
void Print(int n)
{
if (n > 0)
Print(n-1);
System.out.println(n );
}
cosc237/recursion
13
Example #4:
•
•
•
•
Write a recursive function to find n factorial.
n! = n * (n-1) * (n-2)... 3 * 2 * 1
Factorial(5) = 120 = 5 * 4 * 3 * 2 * 1
Base case:
if (n == 1)
return 1;
• General case:
n! = n * (n-1) * (n-2)... 3 * 2 * 1
= n * [(n-1) * (n-2)... 3 * 2 * 1]
= n * (n-1)! OR:
Factorial(n) = n * Factorial(n-1)
4/9/2016
cosc237/recursion
14
Factorial
n! = n x (n-1)!
int factorial(int num)
{
if (num == 0)
return num;
else
return num * Factorial(num – 1);
}
4/9/2016
cosc237/recursion
15
Recursive Factorial Method
(continued)
16
Example #5:
• Write a recursive function to find xn .
• Base case: 20 = 1
• General Case: 2n = 2 * 2n-1
4/9/2016
cosc237/recursion
17
power function
int Power(int x, int n) // n >0
{
if (n == 1)
return x; // base case
else
return x * Power(x,n-1);
}
4/9/2016
cosc237/recursion
18
Power, n<0
• Note that 2-3 = 1/23 = 1/8
• In general, xn = 1/ x-n for non-zero x,
and integer n<0.
4/9/2016
cosc237/recursion
19
Power
float Power (float x, int n)
{
if (n == 0)
// base case
return 1;
else if (n > 0)
// first general case
return (x * Power(x , n - 1));
else
// second general case
return (1.0 / Power(x , - n));
}
4/9/2016
cosc237/recursion
20
Use the box method to trace
• Activation record
• Represent each call to the function
during the course of the execution by a
new box
• Local environment
4/9/2016
cosc237/recursion
21
Tracing a Recursive Method
• After completing a recursive call:
– Control goes back to the calling
environment
– Recursive call must execute completely
before control goes back to previous call
– Execution in previous call begins from point
immediately following recursive call
22
Exercises
void mystery(char param1, char param2)
{
if (param1 != param2)
{
param1++;
param2--;
Mystery(param1, param2);
System.out.println(param1);
System.out.println(param2);
}
}
• Show all output resulting from the following
invocation:mystery('A','G');
• Under what circumstances does mystery result in
4/9/2016
infinite recursion? cosc237/recursion
23
int TermUnknown (int someInt)
// This is a classic number theory problem for which
// termination for all input is uncertain.
{
if (someInt == 1)
return 0;
if (someInt % 2 == 1)
return 1 + TermUnknown(3 * someInt +1);
return 100 + TermUnknown(someInt/2);
}
What
a.
b.
c.
4/9/2016
value does each of the following invocations return?
TermUnknow(1);
TermUnknown(4);
TermUnknown(3);
cosc237/recursion
24
Largest Value in Array
public static int largest(int[] list,
int lowerIndex,
int upperIndex)
{
int max;
if (lowerIndex == upperIndex)
return list[lowerIndex];
else
{
max = largest(list, lowerIndex + 1,
upperIndex);
if (list[lowerIndex] >= max)
return list[lowerIndex];
else
return max;
}
}
25
Largest Value in Array (continued)
26
Recursive Functions
• Recursive function - invokes itself
directly or indirectly
– direct recursion - function is invoked by
a statement in its own body
– indirect recursion - one function initiates
a sequence of function invocations that
eventually invokes the original
• A->B->C->A
4/9/2016
cosc237/recursion
27
• When a function is invoked - activated
• activation frame - collection of
information maintained by the run-time
system(environment)
– current contents of local automatic
variables
– current contents of all formal parameters
– return address
4/9/2016
– pushed on stackcosc237/recursion
28
Linear Search
•
•
•
•
array a
two subscripts, low and high
Key
Return -1 if key is not found in the
elements a[low...high].
• Otherwise, return the subscript where
key is found
29
// Recursive definition
int LinearSearch ( /* in */
/* in */
/* in */
/* in */
{
if ( a [ low ] == key )
const int a[ ] ,
int low ,
int high,
int key )
// base case
return low ;
else if ( low == high)
// second base case
return -1 ;
else
;
// general case
return LinearSearch( a, low + 1, high, key )
}
30
30
Function BinarySearch( )


BinarySearch that takes sorted array a,
and two subscripts, low and high, and a
key as arguments. It returns -1 if key is
not found in the elements a[low...high],
otherwise, it returns the subscript where
key is found
BinarySearch can be written using
iteration or using recursion
31
// Iterative definition
int BinarySearch (int a[ ] , int low , int high,int key )
{
int mid;
while ( low <= high )
{
// more to examine
mid = (low + high) / 2 ;
if ( a [ mid ] == key )
return mid ;
else if ( key < a [ mid ] )
high = mid - 1 ;
else
low = mid + 1 ;
}
return -1 ;
// found at mid
// search in lower half
// search in upper half
// key was not found
}
32
32
// Recursive definition
int BinarySearch (int a[ ], int low, int high, int key)
{
int mid = (low + high) / 2 ;
if ( low > high )
// base case -- not found
return -1;
if ( a [ mid ] < key )
// search in upper half
return BinarySearch( a, mid + 1, high, key ) ;
else if ( key < a [ mid ] )
// search in lower half
return BinarySearch ( a, low, mid - 1, key );
else
return mid;
}
33
33
"One Small Step/Complete the
Solution"
• Each invocation of a recursive function
performs one small step towards the
entire solution and makes a recursive
call to complete the solution.
4/9/2016
cosc237/recursion
34
Recursive Functions
• Non-value-returning
– invoked as separate stand-alone statement
• value-returning
– invoked in an expression
– often embedded within return statement
4/9/2016
cosc237/recursion
35
Recursion or Iteration?
• Two ways to solve particular problem:
– Iteration or Recursion
• Every loop can be replaced by recursion
• not every recursion can be replaced by a loop
• Iterative control structures use looping
to repeat a set of statements
• Tradeoffs between two options:
– Sometimes recursive solution is easier
– Recursive solution is
36 often slower
Factorial(loop version)
int LoopFactorial (int n)
{
int i;
int fact = 1;
for (i = 1; i <= n; i++)
fact = fact * i;
return fact;
}
4/9/2016
cosc237/recursion
37
Factorial - table lookup
• int factorial[8] =
{1,1,2,6,24,120,720,5040};
• faster, can simplify algorithms
• more memory space
4/9/2016
cosc237/recursion
38
Programming Example:
Decimal to Binary
public static void decToBin(int num,
int base)
{
if (num > 0)
{
decToBin(num / base, base);
System.out.print(num % base);
}
}
Java Programming: Program Design
Including Data Structures
39
Programming Example: Decimal
to Binary
Java Programming:
Program Design
40
When to Use Recursion
• If the problem is stated recursively
• if recursive algorithm is less complex
than recursive algorithm
• if recursive algorithm and nonrecursive
algorithm are of similar complexity nonrecursive is probably more efficient
• consider table-driven code
4/9/2016
cosc237/recursion
41
• References:
[1] Programming and Problem Solving with C++,
third edition, by Neal Dale, Chip Weems, and
Mark Headington, Jones and Bartlett Publishers,
2002.
[2] Data Abstraction and Structures Using C++,
by Mark R. Headington, and David D. Riley,
Jones and Bartlett Publishers, 1997.
[3] Starting Out with C++, by Tony Gaddis, Scott
Jones Publishers, 2004. Java Programming:
• [4] Program Design Including Data
Structures,
D.S.
Malik
4/9/2016
cosc237/recursion
42
•