1
RECURSION
Truong Thi Ngoc Phuong
Contents
2
Introduction
Triangular Numbers
Factorials
A Recursive Binary Search
The Towers of Hanoi
Mergesort
3 Introduction
4 Triangular Numbers: Examples
5 Finding nth Term using a Loop
6
Finding nth Term using Recursion
7
Value of the nth term is the SUM of:
The first column (row): n
The SUM of the rest columns (rows)
Recursive method
8
Recursive method
9
Now, it is complete with
stopping condition
See triangle.java program
Recursion Characteristics
10
It calls itself
When it calls itself, it does so to solve a smaller
problem
There is some version of the problem that is simple
enough that the routine can solve it, and return, without
calling itself
Is recursion efficient?
No
Address of calling methods must be remembered (in stack)
Intermediate arguments must also be stored
Factorials
11
Factorials
12
Loop
13 Binary Search: Recursion vs. Loop
Recursion
14 Binary Search: Recursion vs. Loop
Divide-and-conquer
15
Divide problems into two smaller problems
Solve each one separately (divide again)
Usually have 2 recursive calls in main method: one for
each half
Can be non-recursive
Examples
The Towers of Hanoi
MergeSort
Towers of Hanoi
See Towers Workshop Applet
16
An ancient puzzle consisting of a number of disks
placed on three columns (A, B, C)
Objectives
Transfer all disks from column A to column C
Rules
Only one disk can be moved at a time
No disk can be placed on a disk that is smaller than
itself
Algorithm
17
Move first n-1 subtree from S to I
Move the largest disk from S to D
Move the subtree from I to D
18 Algorithm
19 Implementation
20 Merge Sort
Merge Sort
21
Simple Sorting Algorithms: O(N2)
Bubble Sort, Selection Sort, Insertion Sort
Using Sorted Linked List
MergeSort: O(NlogN)
Approach to MergeSort
Merging Two Sorted Arrays
Sorting by Merging
Demo via Workshop Applet
Efficiency of MergeSort
Merging two sorted arrays
22
Given two sorted arrays (A, B)
Creating sorted array C containing all elements of
A, B
Merge Sort
23
Devide an array in halves
Sort each half
Using recursion
Divide half into quarters
Sort each of the quarters
Merge them to make a sorted
half
Call merge() to merge two
halves into a single sorted
array
24 Implementation
25 Implementation
26 Implementation
27 Example
Efficiency of Merge
Sort: O(NlogN)
28
Number of Copies
Copied to Workspace
Copied back to
original array
NEX
T
29 Eliminate recursion
Recursion: inefficient
30
Some algorithms are naturally in recursive form
(merge sort, Hanoi Tower, etc)
But recursion is not efficient
try to transform to non-recursive approach
Recursion & stack
31
Recursion is usually implemented by stacks
Simulating a recursive method
32
Read more on p.294
