The Magic of Recursion in Programming

Recursion

The Magic of Believing in Yourself

as a Programmer

Recursion



Review of Methods



Fractal Images



What is Recursion



Recursive Algorithms with Simple

Variables



Towers of Hanoi

Methods



Named set of instructions



name suggests what the instructions are for

»

println 



 print a line

»

nextInt 



 get the next int

»

setName 



 change the name



what do you suppose these methods do?

»

sort

»

shuffle

»

drawFern

The Job of the Method



Every method has a job to do



print a line, get the next int, draw a fern, …

»

(part of the job may be signalling errors)



Call the method 



 the job gets done



that’s what the method is there for



How

 the method does the job…



the body/definition of the method



…is 

none of the caller’s business

!

Doing The Job



The method does the job



…println(“Hello”) 



“Hello” gets printed



…nextInt() 



 next int appears



…sort(myArr) 



 myArr gets sorted



How?



doesn’t matter!

»

tomorrow it could do it a different way



just matters that the job gets done

Arguments and Parameters



Methods often need extra information



what do you want me to print on the line?



what do you want me to change the name to?



which array do you want to sort/shuffle?



Extra information 

given

 as an argument

buddy.setName(

“Buford”

);



Extra information 

received

 as a parameter

public void setName(

String newName

) { …}

Arguments and Parameters



Assignment call is like assignment

buddy.setName(

“Buford”

);

public void setName(

String newName

) { …}



String newName = “Buford”



Arguments and parameters must match up



String parameter needs a String argument



int parameter needs an int argument



argument order must match parameter order

»

the computer cannot figure it out on its own!

Arguments and Parameters



Different arguments in different calls



printArr(arr1)



 prints arr1



printArr 

(arr2)



 prints arr2



Same parameter every time

public static void printArr(int[] arr)



int[] arr = arr1 on the first call



int[] arr = arr2 on the second call



Arguments 

live

; parameters 

die

Methods and Arguments



The method does its job…



…with the arguments you gave it…



it sorts the array you told it to sort



it prints the line you told it to print



it draws the fern you told it to draw



…because that’s its job!

REMEMBER THAT!

A Fern



Drawing in a

graphics window



Has a root



Has an angle



growing straight up



Has a height

The drawFern Method



A method to draw a fern

drawFern(double x, double y, double angle, double size)



say where we want the bottom of the fern to be

»

how many pixels across (x) and down (y)



say what angle we want the fern drawn at

»

straight up = 180º, flat out to right = 90º



say how big we want the fern to be

»

how many pixels from base to tip



This method 

draws a fern

 – that’s its job!

Drawing the Fern



Window is 800 across

by 600 down



x,y = 400,600



angle = 180



size = 600

»

will be a bit shorter

(room to grow)

Drawing Another Fern



Window is 800 across

by 600 down



x,y = 200,300



angle = 90



size = 400

Exercise:  Draw this Fern



Window is 800 across

by 600 down



root is at centre of

window



angle is 120 degrees



height is 40% of the

window’s height

Compare these Ferns

One Fern is Part of the Other



In order to draw the

big fern, we need to

draw the little fern



In fact, we need to

draw three little ferns,

all rooted at the same

place, all the same

size, but at different

angles

Drawing the Fern



Draw the stem



notice where it ends



Draw each of the

three 

fronds



how to draw the

fronds?

»

we have a method

that can do that!

»

what’s it called?

Drawing the Fern



Draw the stem of the fern



end of the stem is the root of the fronds below



Draw a smaller fern going up to the left



Draw a smaller fern going straight up



Draw a smaller fern going up to the right



Stop drawing when the fern gets too small

to see (say, 1 pixel tall)

Drawing Smaller Ferns



Note where stem ended



that’s the start of each small fern

double[] end = drawStem(x, y, angle, size*0.5);



From 

that

 location



draw smaller fern at new angle…



…40% of the original size

drawFern(end[0], end[1], angle+60, size*0.4);

drawFern(end[0], end[1], angle, size*0.4);

drawFern(end[0], end[1], angle-60, size*0.4);

We need to write this method.

Returns new x,y in an array….

What about this method?

drawFern Function

public void drawFern(double x, double y, double angle, double size) {

   double[] end;

   double length = size * 0.5;

// stem is 50% the (nominal) height

   end = drawStem(x, y, angle, length);

// returns x,y of stem end

   if (size > 1.0) {

       double smaller = size * 0.4;

// smaller ferns 40% of full size

       drawFern(end[0], end[1], angle+60, smaller);

       drawFern(end[0], end[1], angle, smaller);

       drawFern(end[0], end[1], angle-60, smaller);

   }

}

drawStem

 draws the stem, and says where it ended

(so we can use that as the root of the other parts)

drawFern Function

public void drawFern(double x, double y, double angle, double size) {

   double[] end;

   double length = size * 0.5;

// stem is 50% the (nominal) height

   end = drawStem(x, y, angle, length);

// returns x,y of stem end

   if (size > 1.0) {

       double smaller = size * 0.4;

// smaller ferns 40% of full size

drawFern(end[0], end[1], angle+60, smaller);

       drawFern(end[0], end[1], angle, smaller);

       drawFern(end[0], end[1], angle-60, smaller);

   }

}

Recursion



A method that calls itself is said to be

recursive



drawFern method calls itself



drawFern is a recursive method



Each call to the method does the job



using the arguments it’s given!



The computer does not get confused



but 

you

 probably will!

Conditional Recursive Call



Recursive call is 

always

 conditional



usually inside an if or else control



Need some condition to 

stop

 the recursion



otherwise you get a stack overflow error

»

never stops calling itself



drawFern recursive call is conditional on size

if (size > 1.0)

»

if size <= 1.0, recursion stops

Recursive Calls “Bottom out”



Draw 1 fern size 500…



draws 3 ferns size 200…

»

draws 9 ferns size 80…

•

draws 27 ferns size 32…

−

draws 81 ferns size 12.8…

–

draws 243 ferns of size 5.12

–

draws 729 ferns of size 2.048

–

draws STEMS of 2187 ferns of size 0.8+



Each level is drawing smaller ferns



eventually the ferns are less than 1 pixel tall

»

just draws the 

stems

 of 

those

 ferns

Fractals



See the pretty pictures!



http://en.wikipedia.org/wiki/Fractal



http://www.geocities.com/rerewhakaaitu/



XaoS viewer

»

you can download this for yourself



These are “self-similar” objects



smaller pieces of self look like whole thing



like our fern

What is Recursion



Recursion is a kind of “Divide & Conquer”



Divide & Conquer



Divide problem into smaller problems



Solve the smaller problems



Recursion



Divide problem into smaller versions of 

itself



Smallest version(s) can be solved directly

Recursion in drawFern



Problem of drawing large fern broken down

into problem of drawing smaller ferns



Smallest ferns too small to see



draw the stem (a dot)…



…but not the branches (no recursive calls)

Koch’s Snowflake



Fractal image



Draw a triangle, except…



…on each side



draw a smaller triangle sticking out



Keep going!



see the animation on wikipedia

http://en.wikipedia.org/wiki/Koch_snowflake

A Snowflake Edge



To draw an edge from x1,y1 to x2,y2:



draw an edge to 1/3 the distance



turn 60 degrees left



draw an edge 1/3 of the original distance



turn 120 degrees right



draw an edge 1/3 of the original distance



turn 60 degrees left



draw an edge 1/3 of the original distance

Recursion in the Snowflake



Problem of drawing an edge is broken down

into problem of drawing smaller edges



recursion!



Smallest lines just get drawn straight



one or two dots



no recursion



“base case”

Drawing the Snowflake Edge



Need to know



how long the basic edge should be



where to start (x, y)



what direction to go in



Return where we stop



so we can start the next edge from there

Exercise



show pseudo-code for this method

to drawEdge(x, y, angle, length):

1)

2)

…

Definitions and Recursion



Mathematicians like to define things



Mathematicians like to define things

recursively



Recursive definition uses the thing being

defined in its own definition!



Step back: conditional definition

Conditional Definitions



Definition with two (or more) cases

Recursive Definitions



One (or more) cases use the term being

defined

Understanding Recursive Def

n

s



How can you define something in terms of

itself?



Need a BASE CASE



the small case that is defined directly



there may be more than one



Recursive case(s) must get “smaller”



there may be more than one



each case must be “closer” to some base case

Getting Smaller



4! = 4 * 3!

Recursive Case

4 * 6 = 24



3! = 3 * 2!

Recursive Case

3 * 2 = 6



2! = 2 * 1!

Recursive Case

2 * 1 = 2



1! = 1 * 0!

Recursive Case

1 * 1 = 1



0! = 1

Base Case

Base Case

Recursive Case

Recursion in Factorial



Problem of finding factorial of a number

broken down into problem of finding

factorial of smaller number



factorial of n is n times the factorial of n–1



factorial of 0 is 1

Recursive Function Definitions

public static int factorial( int n ) {

  if (n == 0) {        // Base Case

    return 1;

  } else if (n > 0) {  // Recursive Case

    return n * factorial(n-1);

  } else {

    throw new IllegalArgumentException();

  }

}

Base Case

Recursive Case

Calling a Recursive Function



Just like calling any other function

System.out.println( factorial(5) );



The function returns the factorial of what

you give it



because 

that’s what it does



it returns the factorial 

every time you call it



including when you call it inside its definition

120

Recursive Function Definitions

public static int factorial( int n ) {

  if (n == 0)   // Base Case

    return 1;

  else          // Recursive Case

    return n * factorial(n-1);

}

This 

will 

calculate the factorial of n–1

It’s what the factorial function 

does

Recursive Function Definitions

public void drawFern(double x, double y, double angle, double size) {

   double[] end;

   double length = size * 0.5;

   end = drawStem(x, y, angle, length);

   if (size > 1.0) {

       double smaller = size * 0.5;

       drawFern(end[0], end[1], angle+60, smaller);

       drawFern(end[0], end[1], angle, smaller);

       drawFern(end[0], end[1], angle-60, smaller);

   }

}

This 

will 

draw a fern.

It’s what the drawFern function 

does.

Exercise



Write a recursive function to calculate the

(non-negative integer) power of an integer



Hint:  it’ll look a LOT like the one for factorial

Thinking Recursively



Need to recognize smaller versions of same

problem, 

maybe

 slightly changed



these ferns are like those ferns, but smaller

»

and different place and angle



if I had (n–1)! I could just multiply it by n



And think of the 

really

 easy version



a one pixel tall fern is just a dot



0! is just 1

Coding Recursively



Remember the two imperatives:



SMALLER!

»

when you call the method inside itself, one of the

arguments has to be smaller than it was



STOP!

»

if the argument that gets smaller is very small

(usually 0 or 1), then don’t do the recursion

Towers of Hanoi



Buddhist monks in Hanoi



Set the task of moving golden disks (64)

around diamond needles (3)



all disks different sizes



never put a bigger disk on a littler one



When all 64 disks have been moved from

the starting needle to the ending, 

the

universe will end

(In class demo – 4 disks)

What Would be Easy?



What if there were only one disk?

Start Peg

End Peg

Extra Peg

A Little Less Easy



What if there were two disks?

Start Peg

End Peg

Extra Peg

More Disks?

Start Peg (5)

End Peg (5)

Extra Peg (5)

Get top disks “out of the way”  (takes MANY moves)

Towers of Hanoi (5 disks)

Start Peg (5)

End Peg (5)

Extra Peg (5)

Move bottom disk (one move)

Towers of Hanoi (5 disks)

Start Peg (5)

End Peg (5)

Extra Peg (5)

Finish moving the top disks over to the end peg (MANY moves)

Towers of Hanoi (5 disks)

Start Peg

End Peg

Extra Peg

All done!

Towers of Hanoi (Version 1)



If there’s only one disk



move it to the end peg



Else



move the top disks out of the way

»

extra peg becomes end peg for one less disks



move the bottom disk to the end peg



move the top disks onto the end peg

»

start peg becomes extra peg

Towers of Hanoi (3 disks)

Towers of Hanoi (3 disks)

Move 3 disks here

Move 2 disks out of the way

Towers of Hanoi (3 disks)

Move 3 disks here

Move 2 disks out of the way

Towers of Hanoi (3 disks)

Move 3 disks here

Towers of Hanoi (3 disks)

Move 3 disks here

Towers of Hanoi (3 disks)

Move 3 disks here

Move 2 disks here

Towers of Hanoi (3 disks)

Move 3 disks here

Move 2 disks here

Towers of Hanoi (3 disks)

Towers of Hanoi (Version 1)

public void hanoi(int numDisks, char start, char end, char extra) {

if (numDisks == 1) {

S.o.p("Move a disk from " + start + " to " + end);

} else{

hanoi(numDisks – 1, start, extra, end);

S.o.p("Move a disk from " + start + " to " + end);

hanoi(numDisks – 1, extra, end, start);

}

}

Towers of Hanoi (Version 1)

public void hanoi(int numDisks, char start, char end, char extra) {

if (numDisks == 1) {

S.o.p("Move a disk from " + start + " to " + end);

} else{

hanoi(numDisks – 1, start, extra, end);

S.o.p("Move a disk from " + start + " to " + end);

hanoi(numDisks – 1, extra, end, start);

}

}

Common code can be combined

What’s Easier than One Disk?



With no disks, there’d be nothing to do!



with one disk:

»

move zero disks out of the way

»

move bottom disk to end peg

»

mover zero disks onto bottom disk



Exercise



Towers of Hanoi (version 2)

»

simplify the code from the previous slide

Recursive Sorting Method



Merge sort a pile of student papers



if there’s more than one paper in this pile

»

divide it into two equal(ish) piles

»

merge-sort each smaller pile

»

merge the results back together



Much

 faster than inserting each paper into a

sorted pile one at a time



especially on a computer

Binary Search



Searching a sorted List



[1, 3, 4, 4, 7, …, 1204891, 1204893, 1204894]

»

about 1 million elements



Is 600000 in the List?



start at front, looking at every element?



Probably about ½ way thru the List



quicker to just jump to the middle



then look below/above depending on what seen

Binary Search



Is 600000 in the List?



look at middle element



[…, 603450, …]



would 600000 be before or after this position?

»

remember, the list is sorted, lowest to highest



600000 < 603450, so 

if

 600000 is in the list,

it’ll be 

before

 603450



so look for it in the lower half of the list

Binary Search: Smaller Lists



Looking at middle element of sorted List

lets us split the list in two



only have half as many elements to look at



less to look at 



 less time looking



But same principle applies now!



look at middle of remaining elements



go up/down based on what you find



List is getting smaller every time

Binary Search: Stopping



Stop when you find the number



[…, 600000, …] 



 found it!



OR stop when you find out it can’t be there



[…, 599998, 600001, …] 



not in the list

»

must be 

above

 599998

»

must be 

below

 600001

»

but there’s no space between them

»

# of elements we’re looking at has dropped to zero

Binary Search Public Method



Search between positions 0 and size()



return position of element (if found)



return negative number if not found

»

negative number is not a valid position

public static int binarySearch(List<Integer> list, int value) {

    return binarySearch(list, value, 0, list.size());

}

Binary Search Private Method

private static int binarySearch(List<Integer> list, int value, int lo, int hi) {

    if (lo == hi) {

// ran out of places to look

        return -1; 

    } else {

        int mid = lo + (hi – lo) / 2;

        if (list.get(mid) == value) {

// found it!

            return mid;

        } else if (value < list.get(mid)) {

// look below

            return binarySearch(list, value, lo, mid);

        } else {

// look above

            return binarySearch(list, value, mid + 1, hi);

        }

    }

}

Binary Search Time



How long to search a list of 1000 elements?



1

st

 look 



 down to 499 or 500 elements



2

nd

 look 



 down to 249 or 250 elements



3

rd

 look 



 down to 124 or 125 elements



4

th

 look 



 down to 62 or 63 elements



5

th

 look 



 …



…



10

th

 look 



 down to 0 or 1 element



Look at 

at most 

11 elements

Binary Search Time



How long to search 1 000 000 elements?



at most 21 looks



How about 1 000 000 000 elements?



at most 31 looks



The longer the list is, the bigger the savings



maximum number of looks: 

⌈1 

+

 log

2

 N⌉



you do 

not

 want to look thru 1 billion elements

one by one from beginning to end looking for a

number that might not be there!

Recursion, Simplicity & Speed



Recursion generally makes code simpler



less lines, so easier to grasp

»

4 lines for recursive towers of hanoi

»

30-40 lines for iterative (non-recursive)



Sometimes

 it slows things down



recursive fibonacci 

much

 slower than iterative



Sometimes it speeds things up



recursive sorting methods faster than iterative

»

(generally!)

But Some Things are Just Slow



Doesn’t matter 

how

 you do them, they take

a long time



Towers of Hanoi



if it takes 1 second to move each disk each time



how long until all 64 moved to the final peg?

»

1 hour?

»

1 day?

»

1 year?

»

100 years?

»

a million years?

Algorithmic Analysis



Computer scientists study algorithms



find out which way of doing things is fastest

»

on average (how long should we expect it to take?)

»

worst case (what’s the worst that could happen?)



e.g.

 decide whether an ArrayList or LinkedList

would be best for this particular problem



We will start learning about that next term



data structures course (CSCI 2341)

Questions