Transcript ChenRecursive

Recursive Algorithm
By: Lokman Chan
Recursion
Definition: A function that is define in terms of itself.
Goal: Reduce the solution to a problem with a
particular set of input to the same problem
with smaller input values.
Simplify a complex problem to several
sub problems
Examples: Looking up a word from a dictionary (non mathematical)
Solutions to “Towers of Hanol” problem (mathematical)
Merge Sort, reversing a list, binary search, etc…
Lookup a phone number in phone book
Since the phone numbers are listed in alphabetical,
we can actually apply the recursive strategy to find a number
Consider  Search: middle page = (first page + last page)/2
Open the phone book to middle page;
If (name is on middle page)
then done;
//this is the base case
else if (name is alphabetically before middle page)
last page = middle page
//redefine search area to front half
Search
//recursive call with reduced number of pages
else //name must be after middle page
first page = middle page
//redefine search area to back half
Search
//recursive call with reduced number of pages
Towers of Hanoi
The recursive algorithm is based on the observation that moving a
tower of height h from pole A to pole B is equivalent to moving a tower
of height h-1 to pole C, them moving the last disk from pole A to pole B,
and finally moving the the tower from pole C to B.
So the problem of moving a tower of height h, has been reduced
to the one of moving a tower of height h-1.
The idea behind…
Objective:
Move tower of 3 disks from peg a to peg b, with the help of peg c.
Rules:
Only one disk can be moved at a time.
A larger disk can never be placed on top of a smaller disk.
Assume the disk1 is smallest, disk2 is larger and disk3 is largest
1

2
3
_______
_______
_______
A
B
C
2
3
1
_______ _______ _______
A
B
C
More steps …
1
3
1
2
_______
_______
_______
A
B
C

3
2
_______
_______
_______
A
B
C
Steps…
1
3
_______
A
2
_______ _______
B
C

1
3
2
_______ _______ _______
A
B
C
Finally
1
2
1
3
_____
_____
A
B
2

_____
3
_______ _______ ______
C
A
B
It turns out to be a recurrence relationship
and can be computed using recursive algorithm
For better simulations, please go to http://www.cut-the-knot.org/recurrence/hanoi.shtml
C
Merge Sort
Merge sort can be done nicely with recursive algorithm
but can also be implemented without using recursion.
(For demonstration purpose, we will discuss only
recursive merge sort)
Merge sort is a sorting algorithm using
divide and conquer algorithm.
Divide and Conquer
General Strategy:
1) Split the problem into subproblems
2) Solve subproblems
3) Combine the results
http://www.cs.nott.ac.uk/~nza/G5BADS01/slides4.pdf
http://www.cs.nott.ac.uk/~nza/G5BADS01/slides4.pdf
Recursive Merge Sort
1) Split the array into two halves
2) Call merge on each half
3) Merge sorted Halves
Time Complexity
Levels of recursion: log2N
At each level: merging N items
Time complexity: O(N log2 N)
Space complexity: O(N)
Basic foundation of Recursive Algo…
1) Base case(s): There must be at least one base which can
be solved without recursion
2) A recursive call should always making progress, heading
towards the base case. (Simplify the problem)
3) Don’t duplicate work by solving the same instance of a
problem in separate recursive calls (don’t use recursion
instead of a simple loop)
4) Design rule: Assume that all the recursive calls work
Advantages of recursive algorithms
The recursive algorithm gives a more understandable,
code
The actaul code can be expressed with a few lines
of code when defined properly
Disadvantages of Recursive Algo…
Not all mathematically recursive functions can be
efficiently implemented by Java’s simulation of recursion
Infinite recursion can lead to stack overflow if the recursiv
code run (loops) forever
THE END