Transcript Recursion

Recursion
Recursive Definitions


A recursive definition is one which uses the
word being defined in the definition
Not always useful:


for example, in dictionary definitions
In programming it can be very useful…
A Recursive Definition

How do we define a LIST of numbers?



A LIST is either:



2, 65, -34, 4
1, 2, 4, 8, 16, 32
<number>
<number>, LIST
The concept of a LIST is used to define itself
Breaking Down the Definition

The recursive part is used several times:
number comma LIST
2
,
65, -34, 4
number comma LIST
65
,
-34, 4
number comma LIST
-34
,
4
number
4
Form of a Recursive Definition

The base case:


The recursive case:


LIST ::= number
LIST ::= number, LIST
Without the base case, we have infinite
recursion … usually a problem in
programming
A Recursive Function


Compute n!, pronounced “n factorial”
This is the product of all numbers up to and
including n


5! = 5 * 4 * 3 * 2 * 1 = 120
n! = n * (n-1) * (n-2) * … * 2 * 1
A Recursive Function (cont’d)

Think recursively…what is the base case?



what is ‘1!’ ?
How can we write n! in terms by using (n-1)!
The definition:


1! = 1
n! = n * (n-1)!
A Recursive Function (cont’d)

Eventually, the base case is reached:
5! =
5 * 4!
= 120
4 * 3!
= 24
=6
3 * 2!
2 * 1!
1
=2
Recursive Programming

Code in the body of a method can call other
methods


e.g. In Quadratic, root1 calls discrim
There is no reason why a method can not call
itself

e.g. In the body of MyFunc(), we can call
MyFunc()
Recursive Method Declarations



A recursive method declaration must define
both the base case and the recursive case
Each method call has it’s own variables and
parameters
Flow of control is unchanged:

Method executes, then returns control to the
calling method
When Do We Want Recursion?


There are many problems that are easier to
solve with recursive functions
A problem that can be solved in pieces is a
candidate for a recursive algorithm




Chop the function into one or more smaller parts
Solve each part recursively
Combine the parts to a whole solution
e.g. reversing a string
Reversing a String (informal)



Start with “CMPT”
Return reverse(“MPT”) + ‘C’
Base case:


reverse(“”) = “”
Recursive case:

reverse(char + STRING)
= reverse(STRING) + char
Reversing a String (code)
class StringRev
{
public static String reverse(String s)
{
if ( s.length() == 0 )
return s;
else
return reverse(s.substring(1)) + s.charAt(0);
}
public static void main(String[] args)
{
System.out.println( reverse(“CMPT") );
}
}
Analyzing The Method
reverse(“CMPT”) returns reverse(“MPT”) + ‘C’
reverse(“MPT”) returns reverse (“PT”) + ‘M’
reverse(“PT”) returns reverse(“T”) + ‘P’
reverse(“T”) returns reverse(“”) + ‘T’
So:
reverse(“CMPT”) = reverse(“MPT”) + ‘C’
= (reverse(“PT”) + ‘M’) + ‘C’
= ((reverse(“T”) + ‘P’) + ‘M’) + ‘C’
= (((reverse(“”) + ’T’) + ‘P’) + ‘M’) + ‘C’
Understanding Recursion


… but you probably don’t need to worry too
much about those details
When trying to understand a recursive
algorithm


assume the recursive calls return the right thing
look at how that result is used to build the whole
result
Defining Recursive Functions

The idea:






Take the original problem (reverse “CMPT”)
Find a smaller subproblem (reverse “MPT”)
Define solution from subproblem (append ‘C’)
Combine for general solution
If you can do this, you are pretty much done
Key words “smaller subproblem”
“Smaller”

You can’t keep calling reverse(“CMPT”) in the
recursive part



infinite recursion
reverse(“CMPT”)-> reverse(“CMPT”)->
reverse(“CMPT”)-> reverse(“CMPT”)->…..
The recursive step MUST reduce the problem
size
“Subproblem”

You must be able to split the problem to
make a recursive call



When the subproblem gets “obvious” then
you have the base case


subproblems getting smaller is good
e.g. iteratively taking characters from “CMPT”
reverse(“”) = “”
Every input MUST end with the base case
Recursive Programming



Just because we “can” find a recursive
solution, doesn’t mean that we should
Consider summing the numbers 1+…+n
What is the base case?


sum(1) = 1
What is the recursive case?

sum(n) = n + sum (n-1)
Recursive Programming
// This method returns the sum of 1 to num
public int sum (int num)
{
int result;
if (num == 1)
result = 1;
else
result = num + sum (n-1);
return result;
}
Recursive Programming

The iterative version is “easier to understand”


Sometimes you also want to consider
“running time”


Think about the way you usually compute a sum
Is the iterative version faster or slower than the
recursive version?
You need to decide on a case-by-case basis
if recursion provides the best solution
Indirect Recursion

So far we have looked at direct recursion –
when a method calls itself

A method could invoke another method,
which invokes another, etc., until eventually
the original method is invoked again
This is indirect recursion, and it requires the
same care

Indirect Recursion
m1
m2
m3
m1
m2
m1
m3
m2
m3
More Examples



Maze traversal (in text)
Towers of Hanoi (in text)
Calculate xy for positive integer y



This example has several recursive solutions….
There are several ways to break it into
subproblems
The choice you make can have an impact on
efficiency
Powers (version 1)


xy = x * xy-1
base case, x0 =1
public static long pow(long x, long y)
{
if(y==0)
return 1;
else
return (x * pow(x,y-1));
}
Powers (version 1)

xy = xy/2 * xy/2 , base case, x0 =1
public static long pow(long x, long y)
{
long half;
if(y==0)
return 1;
else if(y%2==0) // y even
{
half = pow(x,y/2);
return half * half;
}
else
{
half = pow(x,(y-1)/2);
return (half * half * x);
}
}
Which one is better?



Version 1 requires less code, but…
Version 1 requires y steps to run
Version 2 requires log2(y) steps


This is much faster when y gets big
These differences can matter…


Computing 108 with Version 1 runs out of memory
on a reasonable machine
Computing 108 with Version 2 takes 0.2 sec on
same machine
Running Time


We consider this kind of argument in detail
later… when we discuss “running time”
For now, it is sufficient to remark that you
want to balance elegance and efficiency