# How to mentally keep track of recursion

I have great trouble doing recursion, especially trying to visualize it. A great example is the aging wine problem described in the top answer of this link: https://www.quora.com/Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial. In the example, you are tasked with finding the optimal sequence of wine to sell given the wine's initial prices and the fact that the prices double each year.

``````int p[N]; // read-only array of wine prices
// year represents the current year (starts with 1)
// [be, en] represents the interval of the unsold wines on the shelf
int profit(int year, int be, int en) {
// there are no more wines on the shelf
if (be > en)
return 0;
// try to sell the leftmost or the rightmost wine, recursively calculate the
// answer and return the better one
return max(
profit(year+1, be+1, en) + year * p[be],
profit(year+1, be, en-1) + year * p[en]);
}
``````

Above, I have a hard time visualizing. First I think what the function returns at the end of the recursion, which is a 0, then I try to calculate the value that is returned from the second to last recursion. I can do this for several steps until I get lost.

• The problem here isn't recursion. This is a semantic nightmare. What the heck is "an interval of unsold wines"? What are `be` and `en`? Do you mean begin and end? Why are you multiplying a year by a price? – candied_orange Jul 16 '16 at 1:31
• @CandiedOrange I didn't write that. Its from the link. be and en are indices pointed at the first and last index respectively. You are multiplying year by price since the price increases per year so p_n = p_{n-1} * y_{n-1}. – mrQWERTY Jul 16 '16 at 1:33
• Let the computer do the recursion. Try only to visualize the breaking down of the problem into the next smaller step, and at only one level. – Erik Eidt Jul 16 '16 at 3:25
• It doesn't matter if you didn't write it. You failed to rewrite it. Rewrite it using good descriptive names and meaningful comments . Then try to see how hard understanding recursion is. Bad names are hard to understand using any technique. You're making it harder than it needs to be. – candied_orange Jul 16 '16 at 3:34

Don't try to descend the stack in your head. That way madness lies. By the magic of mathematic induction, every recursive invocation below you can be assumed to be debugged and already working thanks to the programmer who is the future you. Treat it like a call to a library function that you don't have the source code to. If it helps you to work it out, comment it out temporarily and replace it with its results for a test case of reasonable size.

In other words, you don't need to be able to follow the complete algorithm. All you need to know is how to make the problem slightly smaller so you can call an algorithm that already works thanks to recursive you, and write a trivial base case. I can't stress that enough. Trust that the recursive call already works. Once you do that, recursive algorithms become way easier.

• Recursion/induction a great combination of programming and time travel. – Kasper van den Berg Jul 16 '16 at 9:58
• +1 "every recursive invocation below you can be assumed to be debugged and already working thanks to the programmer who is the future you" When reading this all I could think of is Turtls all the way down... as in this xkcd xkcd.com/1416 – Newtopian Aug 16 '16 at 13:40