Department of Computer Engineerin

Recursive Problem Solving

2140101 Computer Programming for International

Engineers
 Department of Computer Engineerin

Objectives

Students should:
• Be able to explain the concept of
recursive definition.
• Be able to use recursion in Java to
solve problems.

2140101 Computer Programming for International Engineers 2

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Recursive Problem
Solving

How to solve problem recursively ?

• Break a problem into identical but sm
aller, or simpler problems.
• Solve smaller problems to obtain a so
lution to the original one.

2140101 Computer Programming for International Engineers 3

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Summation
Alternative Solution:

Let S(n) be the sum of integers from 0 to n.

Mathematically, we can write:
n
S(n)   i
i 0
Java Implementation:
public static int s(int n){
int sum = 0;
for(int i=0;i<=n;i++)
sum += i;
return sum;
} Iterative Approach
2140101 Computer Programming for International Engineers 4
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Summation
Write a method finding the sum of integers from 0 to n

Let S(n) be the sum of integers from 0 to n.

Mathematically, we can write:
S(n  1)  n n 1,2,3,...
S(n) 
0 n 0
Java Implementation:
public static int s(int n){
if(n==0) return 0;
return s(n-1)+n;
} Recursive Approach

2140101 Computer Programming for International Engineers 5

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Summation
Solving S(n) is broken into solving S(n-1),
which is a simpler (but somewhat identical)
problem.
case
A
S(n  1)  n n 1,2,3,...
S(n)  case
0 n 0 B

case
public static int s(int n){
if(n==0) return 0; B
return s(n-1)+n; case
} A

2140101 Computer Programming for International Engineers 6

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Summation
• In finding S(2), method invocation ca
n be depicted as:public static int s(int n){
if(n==0) return 0;
S(2 return s(n-1)+n;
) }

3
S(2)
(s(1)+2)
1
S(1)
(s(0)+1)
0
S(0)
2140101 Computer Programming for International Engineers 7
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Factorial
Write a method finding n!

Mathematically, we can write:

n(n  1) ... 1 n 1,2,3,...

n!
1 n 0

Java Implementation:
public static int factorial(int n){
int s = 1;
for(int i=1;i<=n;i++) s *= i;
return s;
} Iterative Approach
2140101 Computer Programming for International Engineers 8
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Factorial
Write a method finding n!

Alternatively, we can write:

n(n  1)! n 1,2,3,...

n!
1 n 0

Java Implementation:

public static int factorial(int n){

if(n==0) return 1;
return factorial(n-1)*n;
} Recursive Approach
2140101 Computer Programming for International Engineers 9
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Factorial
factorial(4)

24
factorial(4)
(factorial(3)*4)

6 factorial(3)
(factorial(2)*3)
2
(factorial(1)*2)
factorial(2)
1
(factorial(0)*1)
factorial(1)
1
factorial(0)

2140101 Computer Programming for International Engineers 10

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Recursive Method Design

• A recursive method must have two parts.
– Base cases : determine the case where the
recursive method invocation terminates
– Recursive cases : recursive calls itself, but
with simpler parameters
public static int s(int n){
if(n==0) return 0; Recursive cases
return s(n-1)+n;
}

public static intfactorial(int n){

if(n==0) return 1;
Base cases return factorial(n-1)*n;
}
2140101 Computer Programming for International Engineers 11
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Fibonacci
• Example: Fibonacci Numbers (0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89, …)
– The Fibonacci numbers form a sequence of inte
ger defined recursively by:

2140101 Computer Programming for International Engineers 12

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Recursive Method Design

public class FiboDemo
{
public static void main(String[] args)
{
final int n = 20;
for(int i=0;i<20;i++)
System.out.print(fibo(i)+",");
System.out.println();
}
public static int fibo(int n){
if(n<=0) return 0;
if(n==1) return 1;
return fibo(n-1)+fibo(n-2);
}
}

2140101 Computer Programming for International Engineers 13

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Recursive Method Design

fibo(4)

2140101 Computer Programming for International Engineers 14

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Costs of Recursion
• A recursive method accomplishes its task
by successively calling itself.
• Therefore, there are many invocations of
method involved.
• Each time a recursive call is made, a certai
n amount of memory must be allocated.
• For a recursive method that makes very d
eep recursions, a large amount of memory
is required.
Does this mean we should avoid
recursive algorithms ?
2140101 Computer Programming for International Engineers 15
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Fibonacci Numbers Re

visited
import java.io.*;
public class FiboDemo
{
public static void main(String[] args) throws IOException
{ BufferedReader stdin =
new BufferedReader(newInputStreamReader(System.in));
System.out.print("Enter n:");
int n = Integer.parseInt(stdin.readLine());
System.out.println("---Using fibo()------------");
System.out.println("F("+n+")="+fibo(n));
System.out.println("---Using fiboNew()---------");
System.out.println("F("+n+")="+fiboNew(n));
}
public static int fibo(int n){
System.out.println("fibo("+n+") is called.");
if(n<=0) return 0;
if(n==1) return 1;
return fibo(n-1)+fibo(n-2);
}
// continue on the next page
2140101 Computer Programming for International Engineers 16
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Fibonacci Numbers R

evisited
// The same fibo() as the previous example
public static int fiboNew(int n){
int [] remember = new int[n+1];
for(int i=0;i<=n;i++) remember[i]=-1;
return fiboNew(n,remember);
}
public static int fiboNew(int n,int [] r){
System.out.println("fiboNew("+n+") is called.");
if(n<=0){
r[0]=0;
return r[0];
}
if(n==1)
r[n]=1;
else
r[n]=(r[n-1]==-1?fiboNew(n-1,r):r[n-1])
+ (r[n-2]==-1?fiboNew(n-2,r):r[n-2]);
return r[n];
}
}
2140101 Computer Programming for International Engineers 17
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: Fibonacci Numbers Re

visited

From the picture, we

can see that finding t
he 6th Fibonacci num
ber using fibo() requi
res more than three ti
mes as many method
invocations as it is req
uired in the case of us
ing fiboNew().

2140101 Computer Programming for International Engineers 18

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: The Towers of

Hanoi
• Sometimes, the easiest and the least
error-prone ways to write programs f
or solving some problems are recursi
vemethods.
• Sometimes, an iterative approach is
much more difficult than the recursiv
e ones.
• See example “Towers of Hanoi”

2140101 Computer Programming for International Engineers 19

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Towers of Hanoi
Peg Peg Peg
A B C

Goal: Move all disks on Peg A to PegB.

Using minimum number of moves
Rules:
1. Only one disk can be moved at a time, and this disk must
be top disk on a tower.
2. A larger disk cannot be placed on the top of a smaller disk.

2140101 Computer Programming for International Engineers 20

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Towers of Hanoi

2140101 Computer Programming for International Engineers 21

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: The Towers of

Hanoi
import java.io.*;
public class TowerOfHanoiDemo
{
public static void main(String[] args)
throws IOException{
BufferedReader stdin =
new BufferedReader(new
InputStreamReader(System.in));
System.out.print("Enter number of disks:");
int n = Integer.parseInt(stdin.readLine());
move(n,"A","B","C");
}
// continue on the next page

2140101 Computer Programming for International Engineers 22

INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: The Towers of

Hanoi
public static void move(int n,
String orgPole,String destPole,String otherPole){
String step;
if(n<=1){
step = "Move Disk1 from Peg "+orgPole+" to Peg
"+destPole;
System.out.println(step);
}else{
move(n-1,orgPole,otherPole,destPole);
step = "Move Disk"+n+" from Peg "+orgPole+" to
Peg
"+destPole;
System.out.println(step);
move(n-1,otherPole,destPole,orgPole);
}
}
}
2140101 Computer Programming for International Engineers 23
INTERNATIONAL SCHOOL OF ENGINEERING
CHULALONGKORN UNIVERSITY
 Department of Computer Engineerin

Example: The Towers of

Hanoi

Try solving it using an iterative ap

proach.
2140101 Computer Programming for International Engineers
INTERNATIONAL SCHOOL OF ENGINEERING 24
CHULALONGKORN UNIVERSITY