COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 9-2 : Recursion 1
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Recursive algorithms
EXAMPLE
public static void countdown(int n) { if (n == 0) {
System.out.print(“Go!”); } else {
System.out.print(n + “ ”);
countdown(n-1); }
}
What prints if we call countdown(3)? 3 2 1 Go!
EXAMPLE – EXECUTION
Execution of countdown(3).
The execution of countdown starts with n==3. Since it is
not 0, 3 is printed and countdown is called with input 2
o The execution of countdown starts with n==2. It is not 0, thus 2 is printed and countdown is called with input 1.
The execution of countdown starts with n==1. Since it is not 0, 1 is printed and countdown is called with input 0.
The execution of countdown starts with n==0. Since n is 0, Go! is printed and the execution ends.
The execution of countdown(1) ends. o The execution of countdown(2) ends.
The execution of countdown(3) ends and we are back in main.
public static void countdown(int n) { if (n == 0) {
System.out.print(“Go!”); } else{
System.out.print(n + “ ”);
countdown(n-1);
}
}
RECURSIVE – DEFINITION
Recursive functions/methods consists of the following
Base Case(s): one (or a finite number) of terminating scenario that does not use recursion to produce an answer.
Recursive or Inductive step(s): rules that determine how to produce an answer from simpler cases.
BASE CASE
Note that if there is no base case in a recursive method, or if the base case is never reached, the execution will never end.
public static void forever (int n) {
forever(n);
}
COMING UP
Several examples of algorithms that can be implemented recursively: Factorial function
Fibonacci numbers
reverseList
sortList
towerOfHanoi
EXAMPLE 1 – FACTORIAL
The factorial of a number is defined as follows:
0! = 1
1! = 1
2! = 1 ∗ 2 = 2
3! = 3 ∗ 2 ∗ 1 = 6
…
𝑛! = 𝑛 ∗ (𝑛 − 1) ∗ (𝑛 − 2) ∗ (𝑛 − 3) ∗ … ∗ 1
FACTORIAL: RECURSIVE DEFINITION
Notice that:
𝑛! = 𝑛 ∗ (𝒏 − 𝟏) ∗ (𝒏 − 𝟐) ∗ (𝒏 − 𝟑) ∗ … ∗ 𝟏
= 𝑛 ∗ (𝒏−𝟏)!
Thus, the following definition completely determines the factorial:
Base case: 0! = 1
Recursive step: 𝑛! = 𝑛 ∗ (𝑛 − 1)!
FACTORIAL (ITERATIVE)
public static int factorial (int n) {
int result = 1;
for(int i=2; i<=n; i++) {
result = result * i; }
return result;
}
FACTORIAL (RECURSIVE)
Let’s use its recursive definition to write a method that computes the factorial function:
public static int factorial (int n) {
if (n == 0) {
return 1;
}
return n * factorial(n-1);
}
Base case
Induction step
FACTORIAL: AN EXAMPLE
What happens when the method call factorial(4) is executed?
Factorial(4)
Factorial(3)
Factorial(2)
Factorial(1)
Factorial(0)
returns 24
returns 6
returns 2
returns 1 returns 1
public static int factorial (int n) {
if (n == 0) {
return 1; }
return n * factorial(n-1);
}
CORRECTNESS
Claim: the recursive factorial(n) algorithm returns 𝑛! . Proof (by mathematical induction):
Base case: factorial(0) returns 1.
Induction step:
IH: Assume factorial(k) returns 𝑘! when 𝑘 ≥ 1
To prove: factorial(k+1) returns 𝑘 + 1 ! factorial(k+1) returns factorial(k)∗ (𝑘 + 1)
= 𝑘!∗(𝑘+1),byIH = (𝑘+1)!
EXAMPLE 2 – FIBONACCI NUMBERS
Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Base cases:
𝑓=1 1
𝑓=1 2
Recursive/Inductive Step:
𝑓=𝑓+𝑓
𝑛 𝑛−1 𝑛−2
FIBONACCI (ITERATIVE)
public static int fibonacci(int n) {
if(n==0 || n==1) {
return 1; }
fib0 = 1;
fib1 = 1;
for(int i=2; i<=n; i++) {
fib2 = fib0 + fib1;
fib0 = fib1;
fib1 = fib2;
}
return fib2;
}
FIBONACCI (RECURSIVE)
public static int fibonacci (int n) {
if(n==0 || n==1) {
return 1; }
return fibonacci(n-1)+fibonacci(n-2); }
This is much simpler to express than the iterative version.
CORRECTNESS
Claim: the recursive Fibonacci algorithm is correct. Proof(sketch): (by strong mathematical induction)
Induction step:
IH: Let 𝑘 ≥ 0, Assume fibonacci(i) returns 𝑓 for every 0 ≤ 𝑖 < 𝑘 𝑖
To prove: fibonacci(k) returns 𝑓 𝑘
However, the recursive Fibonacci algorithm is very inefficient. It computes the same quantity many times, for example:
fibonacci(247)
fibonacci(246) fibonacci(245)
fibonacci( 245 ) fibonacci( 244 ) fibonacci(244) fibonacci(243)
fibonacci(244) fibonacci(243) fibonacci(243) fibonacci(242) Etc.
EXAMPLE3: REVERSINGALIST
input {𝑎,𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,h} output {h,𝑔,𝑓,𝑒,𝑑,𝑐,𝑏,𝑎}
EXAMPLE3: REVERSINGALIST
input {𝑎,𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,h}
output {h,𝑔,𝑓,𝑒,𝑑,𝑐,𝑏,𝑎} Idea of recursion:
𝑎 {𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,h} {h,𝑔,𝑓,𝑒,𝑑,𝑐,𝑏} 𝑎
REVERSING A LIST (RECURSIVE)
public static void reverse(List list) {
if(list.size()==1) {
return; }
firstElement = list.remove(0); // remove first element
reverse(list); // now the list has n-1 elements
list.add(firstElement); // appends at the end of the list
}
EXAMPLE4–SORTINGALIST (RECURSIVE)
public static void sort(List list) {
if(list.size()==1) {
return; }
minElement = removeMinElement(list);
sort(list); // now the list has n-1 elements
list.add(0, minElement); // insert at the beginning of list
}
EXAMPLE 5 – TOWER OF HANOI
Tower A Tower B Tower C (start) (finish)
Problem: Move n disks from start tower to finish tower such that:
- move one disk at a time
- you can have a smaller disk on top of bigger disk (but you can’t have a bigger disk onto a smaller disk)
EXAMPLE - n=1
start finish
start finish
EXAMPLE - n=2
start finish
from A to C
start finish
EXAMPLE - n=2
from A to B
start
finish
from C to B
start
finish
HOW SHOULD WE MOVE 5 DISKS FROM A TO B?
start finish Let’s think about it recursively!
IDEA!
Somehow move 4 disks from A to C
move 1 disk from A to B
Somehow move 4 disks from C to B
ALGORITHM
tower(n, start, finish, other) { // e.g. tower(5,A,B,C)
if(n==1) {
move from start to finish.
} else {
tower(n-1, start, other, finish) tower(1, start, finish, other) tower(n-1, other, finish, start)
} }
EXAMPLE
tower(4,A,C,B)
tower(1,A,B,C)
tower(4,C,B,A)
CORRECTNESS
Claim: the tower( ) algorithm is correct, namely it moves the blocks from start to finish without breaking the two rules (one at a time, and can’t put bigger one onto smaller one).
Proof: (sketch)
Base case: tower(1,*,*,*) is correct.
Induction step:
for any k > 1, assume tower(k,*,*,*) is correct Prove tower(k+1,*,*,*) is correct.
HOW MANY MOVES?
tower(1, start, finish, other )
Answer: 1
move from start to finish
HOW MANY MOVES?
tower( 2, start, finish, other )
tower( 1, start, other, finish)
move
move
tower( 1, other, finish, start )
move
Answer: 1 + 2
move from A to C
move from A to B move from C to B
HOW MANY MOVES?
tower( 3, start, finish, other )
tower( 2, start, other, finish)
move
tower( 2, other, finish, start )
move
move move
move
move
move
Answer:
1+2+4 = 20 +21 +22
HOW MANY MOVES?
tower( n, start, finish, other )
tower( n – 1, start, other, finish) move
move
tower( n – 1, other, finish, start )
move
… move … … move …
Answer: 1+2+4+ …+ 2𝑛−1 = 2𝑛 −1
…
move … … move …
RECURSION AND ITERATION
Recursion and iteration (loops) are equally expressive. Anything recursion can do, iteration and do
Anything iteration can do, recursion can do
RECURSION VS ITERATION
Which one to use?
Use the one is easier to think in terms of, for a specific
problem.
For simple cases, iteration is usually easier and faster.
For complex cases, recursion is often more elegant and simpler to code.
It is important to remember that when using one or the other, this decision might impact the performance of your program.
RECURSIVE DATA STRUCTURE
We can recursively defined also data structures.
Let’s consider arrays and let’s think how we can recursively defined a list of items.
LINKEDLIST
LinkedList
private LinkedList
3
5
2
8
-4
myList
In the next videos: Binary Search