Question

Every time I think I'm starting to get recursion...
I'm trying to understand lecture 13 maxVal().
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/lec13.pdf
I'm having alot of trouble following it. Does anyone have a plain english explanation of it or some kind of simple diagram or even just some strategic places to put print statements. I'm sure when I finally "get it", I'll wonder why it took so long! All points in the right direction appreciated...Thanks

Answer 1

Recursion is a process where the next step depends on the results of the step before it. For example, if you were going to hike a mountain path you would do a mental check of your physical energy and take a step. Now in order to make it the length of the path you would need to repeat this process until you reached the end, or ran out of energy.
If this were a computer program you would have a function called 'step' for example, and you would call it with your current energy level. You will always check your "base" conditions prior to the body of the function since there is no reason to keep looking if you have reached where you want to be.The function would only care about where you are now and the next step as anything beyond that is irrelevant. So, if energy was greater than minimum, take another step() where you would pass your current energy level.

def step(energy):
if energy == 0:
return energy
else:
energy = energy -1
step(energy)

With this function we would keep walking until we ran out of energy, the same logic applies with lecture 13.
Since the maxVal() example works off of the backpack problem, you have to decide what items can fit with a given max weight. So starting from the highest index value you step into the function and will actually make two recursive calls, one to reject the object and one to take the object.
Notice that the first recursive call is to "NOT" take an item, if you do not take the object you are telling your function to look at the next item and that you still have the same available space as you did before.
If you look carefully at the code you will notice that the function runs the index to zero down the "without_i" path first and only after hitting zero does it start considering whether or not to take an item as it returns back to the top.

This site has some very cool java animation that visually demonstrates recursion: http://www.animatedrecursion.com/simple
As for some well placed print statements, I would suggest you start by uncommenting the existing statement and consider adding a couple more to reflect all of the values present within the function. As it steps through the recursion you will be able to watch the values tick through their progression.

Answer 2

maxVal mimics stepping thru the decision tree shown in the lecture

start with a small test dictionary and make your own decision tree then step thru maxVal while stepping thru the decision tree to see how maxVal works

here is one with print statements: http://dpaste.com/744150/

Answer 3

Thanks everyone for your help. While I probably wouldn't be able to recreate the function on my own(yet!), I do think I'm getting the hang of it. I used some print statements that had '1's' and '0's' for flags and some plain English as well. I also used raw_input() to sort of slow things down. Well, I'm off to do the actual assignment now so I'm sure you'll "hear" from me again....