Recursion Problems �& Complexity Analysis

Chapter 12.2

Recursion

• There are two basic ways to make things happen "over and over again" in programming
• Loops
• Recursion
• In theory, anything you can do with loops, you can do with recursion (& vice versa)

A Loop That "Counts" From 1 To 10

​

public void count() {

for(int nI = 1; nI <= 10; nI++)

System.out.println(nI);

}

​

A Recursive Function that "counts" from nTimes to 10

public void count(int nTimes) {

if(nTimes == 10){

System.out.print(nTimes + "Stop!");

} else {

System.out.println(nTimes);

count(nTimes+1);

}

​

}

Recursion: �A method that calls itself

• Recursion is another way of making a loop
• Recursion is hard to control—it's very easy to create an infinite loop that never stops

In Recursion, The Stopping Point Is Called The Base Case

public void mystery(int nTimes) {

​

if(nTimes == 0) {

System.out.println("Stop!");

} else {

System.out.println(Math.random());

mystery(nTimes-1);

}

​

}

​

• Every recursive method must have a base case
• The base case is where the recursion stops

​

Just like a loop, it has a starting point, a stopping point, and a way to get from one to the other

public class Recursion extends Applet {

public void init() {

count(1);

}

public void count(int nTimes)

{

if(nTimes == 10)

System.out.println(nTimes + " Stop!");

else

{

System.out.println(nTimes);

count(nTimes+1);

}

}

}

Head vs. Tail Recursion

• The position of the recursive call in a recursive method can have a BIG effect on the way the method works
• If the recursive call is at the end of the method, it's called tail recursion
• If the recursive call is at the beginning of the method, it's called head recursion

Tail Recursion

public void tailRecursion(int nNum) {

​

if(nNum >= 10) {

System.out.println("base case");

} else {

System.out.print(nNum + ", ");

tailRecursion(nNum + 1);

}

​

}

Head Recursion

public void headRecursion(int nNum) {

if(nNum >= 10) {

System.out.println("base case");

} else {

headRecursion(nNum + 1);

System.out.print(nNum + ", ");

}

}

Head vs. Tail Recursion

• Tail recursion works like you would expect, it goes forward
• Head recursion "stacks up" and then "unwinds", it goes backward

Complexity Analysis

Complexity Analysis

• Complexity Analysis
• Process of deriving a formula that expresses the rate of growth of work or memory as a function of the size of the data or problem that it solves.

​

• WHY????
• To see how fast something will run or how much of a memory hog it will be…

​

Big-O Notation

• Big-O Notation
• Formal notation used to express the amount of work done by an algorithm or the amount of memory used by an algorithm.

​

​

• See the video in Moodle.

Big-O | comp. for 10 things comp. for 100 things

---------------------------------------------------------------------

O(1) 1 1

O(log(n)) 3 7

O(n) 10 100

O(n log(n)) 30 700

O(n^2) 100 10000

​

​

​

So take quicksort which is O(n log(n)) vs bubble sort which is O(n^2). When sorting 10 things, quicksort is 3 times faster than bubble sort. But when sorting 100 things, it's 14 times faster! Clearly picking the fastest algorithm is important then. When you get to databases with million rows, it can mean the difference between your query executing in 0.2 seconds, versus taking hours.

​

Big-O Example from Harvard

• The big-O complexity of an algorithm is important, but it does not tell the entire story. Any honest and complete analysis of an algorithm should attempt to address the question of what the real cost of executing the algorithm is for real or typical problems.
• For example, imagine that (through some some wonderful twist of fate), you must choose between job offers from two companies. The first company offers a contract that will double your salary every five years. The second company offers you a contract that gives you a raise of $1000 per year. Your salary at the first company increases at, while your salary at the second company increases at a rate of O(n). Which position would you choose?

Big-O Example from Harvard

• From this information, it is impossible to say. If your starting salaries are the same at the two companies, then what the starting salary is will make all the difference (and if the first company gives you a starting salary of $0, then you are really in trouble!). If the starting salary at the second company is much higher than the first company, then even the wonderful raises the first company offers might not actually make any difference before you retire. In this case, n isn't going to get too large (assuming an ordinary career), so the behavior of your salary as you become infinitely old is not an issue.