Recursion (you have seen it before)
- spam and Chain letters
AN IRISH FRIENDSHIP WISH
Good Luck!! I hope it works...
May there always be work for your hands to do;
May your purse always hold a coin or two;
May the sun always shine on your windowpane;
May a rainbow be certain to follow each rain;
May the hand of a friend always be near you;
May God fill your heart with gladness to cheer you.
OK, this is what you have to do....
Send this to all of your friends! But - you HAVE to send this within 1 hour from when you open it!
Now.................Make A wish!!!!!!
I hope you made your wish! Now then, if you send to:
1 person --- your wish will be granted in 1 year
3 people --- 6 months
5 people --- 3 months
6 people --- 1 month
7 people --- 2 weeks
8 people --- 1 week
9 people --- 5 days
10 people --- 3 days
12 people --- 2 days
15 people --- 1 day
20 people --- 3 hours
If you delete this after you read it... you will have 1 year of bad luck! But... if you send it 2
of your friends you will automatically have 3 years of good luck!!! :-)
- Asexual reproduction
BacteriaPlan: grow yourself, when you are large enough
split in two. Each of you now follows the BacteriaPlan.
- Sexual reproduction
PeoplePlan: grow yourself, when you are old enough,
repeat: find someone to have a baby with and have a baby.
The baby follows the PeoplePlan.
- Ponzi scheme (as in Madoff arrested in alleged Ponzi scheme
- Pyramid scheme:
The Plan:
Find 2 people (p and q)
Sell this plan to them for $4
Make sure that p and q follow this plan
Send 50% of what p and q send you to
the person that sold you this plan.
Problem Solving with Recursion
Recursion is a problem solving technique which uses recursion to solve problems
In general it looks like...
def solve(p):
if p is simple enough:
s=simple solution to p
else:
break p into problems p1,...,pk where
each of p1,...,pk 'looks like' p
each of p1,...,pk is 'simpler' than p
s1=solve(p1) # recursive call to solve
s2=solve(p2) # recursive call to solve
.
.
.
sk=solve(pk) # recursive call to solve
# combine the solutions to the smaller problems
# into a solution s for p (our current problem)
s=combine(s1,...,sk)
return s
-
Consider a checkerboard which has dimensions 2^2000 by 2^2000. Now remove 1 square. You
want to tile the checkerboard with L shaped tiles.
You must not cover the 'removed' square. Prove that, no matter which square you remove, you
can always completely tile the resulting checkerboard.
A tile looks like ...
o
oo
- Prove that an arrangement of n lines in the plane can be colored using at most 2 colors.
You are coloring the regions bounded by the lines.
No edge can have the same color on both sides.
That is, two adjacent regions (sharing an edge) can not have the same color.
twoColour.py
- Print a triangle A of height n recursively
x
xx
xxx
xxxx
xxxxx
xxxxxx
- Print a triangle V of height n recursively
xxxxxx
xxxxx
xxxx
xxx
xx
x
triangles.py
- Why are spirals and trees recursive? drawingRecursively.py
- Print 1 to n recursively. Print n to 1 recursively. Sum up numbers from i to j recursively. sum.py
- McNugget problem (which amounts are buyable):
In McDonalds, you can purchase packs of 4, 6 and 10 McNuggets.
Call a number n buyable if you can purchase packs
summing up to a total of exactly n McNuggets.
Clearly 4,6 and 10 McNuggets are buyable.
16 is buyable (10+6).
Is 23 buyable?
Is 197 buyable?
Is n buyable?
- How do I sort recursively? Searching and Sorting