Matlab Recursion Problem - Need help Understanding It

[Nano-Passion]

They give me this problem in my last exam, I did not get it right - its a very convoluted and I think poorly worded problem. Rants aside, how am I supposed to be able to answer a problem like this on the next exam? What sort of mindset will help me deal with recursion problems of this form? How does this problem work mathematically?

Naturally I would solve this problem using for loops and if statements. I'm not sure what sort of mathematical method is being used here.

Homework Statement

Suppose you had a vector v of numbers and you want to know if some subset of these numbers
adds up to a target number, t. E.g. if v is [3 2 4] and t is 7, the answer is true because the sum
of 3 and 4 is 7. If t is 8 the answer is false because there is no way to add up any subset of 3, 2,
and 4 to get 8. The function subsetsum answers this question using the following recursive
reasoning. Finish subsetsum. Your definition must be recursive. You may assume that t and
every element of v are positive.
◦ If v has length 0, there are no numbers to add so the result is 0 (i.e. false).
◦ If t is equal to the first number in v, the result is 1 (i.e. true).
◦ Let v1 be v without its first number. E.g. if v is [3 2 4] v1 is [2 4]. If you can find a
subset of v1 that sums to t the result is of subset(v, t) is 1.
◦ Also, if you can find a subset of v1 that sums to t-v(1) the result is of subset(v, t) is 1.
◦ Otherwise the result of subset(v, t) is 0.

So I know the answer to this which is:

[1] function res = subsetsum(v, t)
[2] if length(v) = = 0
[3] res=0;
[4] elseif t = = v(1)
[5] res=1;
[6] elseif subsetsum(v(2:length(v)), t)
[7] res = 1;
[8] elseif subsetsum(v(2:length(v)), t-v(1))
[9] res=1;
[10]else
[11]res = 0;
[12]end

So here is my best guess of what is going on for a vector of [3 2 4] with t = 7

subsetsum([3 2 4], 7)
length (v) == 0? No. go on
t == v(1). 7==3? no. go on.

subsetsum([2,4], 7) recursive call to top
length(v) == 0? No. go on
t ==v(1)? 7 == 2? No. go on
Line [6]-[7] not true, jump to line [8]

subsetsum([2 4], t-v(1) = 7- 3 = 4) recursive call to top subsetsum([2 4], 4)
length(v)==0? No. go on.
t = v(1)? 4 = 2? No. go on

back to recursive call line [6]
subsetsum([2 4], 4) recursive call to top
length(v)==0? No.
t == 2? no.
Line [6]-[7] not true, jump to line [8]

subsetsum([2 4], t - v(1) = 4 - 2 = 2) recursive call to top subsetsum([2 4], 2)
length(v)==0? No.
t = v(1)? 2 = 2? Yes. end if.

res = 1.

 

[recurFactor]

I once had a very good CS professor who always likened recursion to solving the simplest possible problem (the base case) and then being lazy and re-using it (reducing the problem to the simpler form). What's your background? (Your use of "jump" has me a bit nervous and most CS types I know of avoid MATLAB like the plague)

First off, can you identify your base cases? I count 3, but some people might express it differently so you might have more or less. There are also a couple of important logic statements here that you might find important to see.

I find it easier to think in the construction than the procedure (unlike how you might do it for loops). Mathematically, recursion proofs tend to be very closely linked to proof by induction, if that's any help.

 

[Nano-Passion]

Hey recurFactor,

I'm majoring in biomathematics for undergrad. To me the first two conditions seem to be the base cases, and the rest aren't because they are making recursive calls.

Base case 1: if length(v) == 0
Base case 2: if t == v(1)
Not sure if this would be a base case since it comes after the recursive calls - else res = 0;. But I wouldn't know what to call it either.

What is mathematical version of this program? I can grasp the steps but it is hard for me to justify what is going on. I'm going to try to lay this out visually, come back, and see if it clicks.

 

[Nano-Passion]

Nevermind, I can see that it works but I have no idea how it works. There is no way I can discern its mechanism without being able to look at its underlying principles. There is probably a good mathematical proof behind this convoluted non-intuitive method- I hope.

I will give it credit: the method is very clever. It looks like it drastically cuts the computing time vs if you were to try to find a subset that adds to t randomly. Of course though, I haven't tried to calculate the big old O out of laziness.

 

[recurFactor]

Actually, you're right about 2. I was going to add the case where we find the sum somewhere else, but that's probably because I haven't had identify a base case for several years and have gotten rusty. It's also my first time trying to help someone over the internet and I'm not used to not hearing my own mistakes as they are coming out (nor am I used to seeing the solution already written out). :P

"else res=0" is a result of how they structured it in MATLAB. Don't pay much attention to it. It basically accounts for the possiblity both recursive calls fail to find the required subset. ("if A then X else if B then X otherwise Y" is equivalent to saying "if A or B then X else Y". See if you can see why this is the case.

The only thing left to think about is what happens with the recursive calls. You are taking one element (v1), considering it (does v1==t?) then removing it from consideration (v(2:length(v)))
1) What is the size of the new set? I think you already have this one and probably why it's important.
2) Suppose we have a subset that forms the sum. What are the two cases for any particular element (say, for convienence, v1)? The answer to this question maps directly to the choice of the recursive calls. Hopefully you should be able to see why you can consider all cases for a given size set with these two considerations alone.
3) rather take a total of the elements we decide to sum, the solution subtracts from the target. It is probably more intuitive to instead keep a running sum of all numbers you have decided to add together and pass it in as an additional input parameter (so you would ask "does v1+alreadySummed==totalTarget" instead of "v1==t" and pass in "alreadySummed+v1, t=totalTarget" instead of "t-v1"). The method they give is slightly less intuitive but more elegant. See if you can see why both options work.

If it helps you understand it, don't be afraid to go from your base case to your general case by adding in an element instead. Realize that your recursive calls (after the base case) are effectively your inductive step, where you generalize from the base case to the general case, so the recursive calls are a reflection of the questions I just asked. How used to induction are you?

I think you are very close to understanding it. Care to elaborate what you mean by "that it works" but not "how it works?" Is the concern to try and figure out how to write the answer the next recursive assignment or are you trying to get a rigorous proof that the program will always return 1 iff there is a subset sum?

 

[Nano-Passion]

Sorry for the brief response, I have an exam early tomorrow. I won't need this for the exam so no rush.

I have a question about what I did before, written below.

subsetsum([3 2 4], 7)
length (v) == 0? No. go on
t == v(1). 7==3? no. go on.

subsetsum([2,4], 7) recursive call to top
length(v) == 0? No. go on
t ==v(1)? 7 == 2? No. go on
Line [6]-[7] not true, jump to line [8]

subsetsum([2 4], t-v(1) = 7- 3 = 4) recursive call to top subsetsum([2 4], 4)
length(v)==0? No. go on.
t = v(1)? 4 = 2? No. go on

Shouldn't v(1) have been 2 instead of the previous 3. If so, I might understand the problem less than I thought.

back to recursive call line [6]
subsetsum([2 4], 4) recursive call to top
length(v)==0? No.
t == 2? no.
Line [6]-[7] not true, jump to line [8]

subsetsum([2 4], t - v(1) = 4 - 2 = 2) recursive call to top subsetsum([2 4], 2)
length(v)==0? No.
t = v(1)? 2 = 2? Yes. end if.
res = 1.

 

[recurFactor]

Yes. It should have been 2. Sorry, I missed that when first scanning your question. I thought you were looking more for a conceptual understanding why the program works than the exact sequence with which the program executes. You will find that many more calls are made than what you have written here.

If you are trying to trace the code execution, try copying the program into MATLAB and using the debugger (see: http://www.mathworks.com/help/matlab/matlab_prog/debugging-process-and-features.html#brqxeeu-182). Remember you can see the value of the variable by hovering your mouse over it.

Are you familiar with the stack? It's important to remember that each time you make a recursive call, it is as if you have a whole new set of variables--subsetsum([2,4],7) is different from subsetsum([3,2,4],7) and is different from subsetsum([3,2,4],4). So when you make a recursive call, you are not "jumping" to a line, you are starting over with a whole new set of variables and the previous call that called the current execution will not continue where it left off until your current call finishes (and this will happen again if your current call makes another recursive call).

This is actually the brute force solution and you should be able to see how examines quite a few possibilities before finding the subset [3,4].

 

[Nano-Passion]

Sorry for the late reply, but thanks a lot recurFactor.