Hi,

My assignment:


I implemented the function as returning a bool value. Using the numbers provided in the example, my function is finding the correct subset (and I can force it to show the subset) , but when the function returns, it always returns a value of false. I can't figure out what it is about the way the recursion unwinds... it gets to the stopping case, sets the value to true, and should be returning that value all the way to the end - yet when the function returns to main, main reports that the value is false.

log shows:

I know I could implement the function as void, returning the bool value by reference, but would rather figure out what the hell is going on!

First thing I'd do is remove isTrue from the parameter list. Set it to false when you enter s().

Then when you call s() within s(), store the return value in isTrue:
That's what you forgot.

__________________

Got a cough? Go home tonight and eat a whole box of Ex-Lax. Tomorrow, you'll be afraid to cough.
-- Pearl Williams

Ah, thanks! I could also just return the results of s:


or for the stopping case


which would negate needing variable
in the called function, correct?

Is that better, do you think?

It's a style issue. I personally prefer not to return a function's return value directly, like return func(); but there's no reason why you can't. I like to keep my statements simpler. As I said, personal style.

__________________

Got a cough? Go home tonight and eat a whole box of Ex-Lax. Tomorrow, you'll be afraid to cough.
-- Pearl Williams

First of all, someone once reported that he read in a book that "recursion is often used to solve problems that would be difficult to solve otherwise, and that recursive functions often are less efficient but easier to understand."

Well, "easier" is a really subjective term, but I'll just say that for cases like this one, it's pretty "easy" for me to visualize what I want to do, and it looks like recursion. It is certainly possible to to this with loops, but let's go for the "easy" way. The trick is to keep it looking "easy" after all of the program requirements are met.

In general, and in simplest terms, a recursive function looks like this


Actually the "else" is redundant here, since the only way it could get to that part is if it hasn't met the stopping condition. But I like to have it as explicit as possible for my own sanity (or whatever approximation that I can pretend to possess).

While we are at it, I note that the last "return" is redundant (at least in C aand C++), since the function returns automatically by "falling off of the end" of the code. (Note that in this simplest form there isn't any provision for a return value.)

If we do define the function to return a value, then we have to keep in mind that after some recursive calls, the function goes through a number of returns before falling off of the end of the page. I'm thinking that's what you refer to as "unwinding". As you mentioned, the unwinding part can be kind of tricky.

Keeping this in mind, the simple, "easy", pseudo code for C (or C++) functions actually might be written with fewer keystrokes something like this:


Or, even, by removing the redundant 'else' and 'return':


Compare any one of these schemas with your program. I'm not saying there is anything "wrong" with your efforts, but the "easier" way gets kind of messy.


First of all, I'm not too crazy about the problem statement: "...find a subset of numbers..." Does it say what you are supposed to do with it? Let's suppose for a minute that all you need to do is print out the subset when you find it, rather than returning that information, somehow, to main(). It really didn't say what to do, so I'll to the "easy" thing.

Then the pseudo code could look like the following (where I have put in a couple things specific to our present problem, and I've made the "pseudo" code look a lot like C++). I have assumed that the parameters of the function are:

set[], size, target, subset and sum, just like yours. What you called "x", I'll call "start": the current index value. The function is called from main() with start = 0 and sum = 0


That is, literally, the whole function (well you actually have to edit two statements and make a function to print the vector, but I hope you get the idea).

If you are one of those wild and crazy guys who like to put comments in your code to remind yourself what the heck it's doing when you come back to it at some later date, you could put the following in the function, just before the loop

Notice, there are no issues with return values. Notice also, that without some extra effort, there's really no way to stop without going through all possible subsets. However it does meet the stated assignment of "finding a subset whose total is that sum". I know, I know...It doesn't satisfy the part about "indicate that none exists otherwise". But I'll get to that in a minute.

I would like to note, at this point, the other thing that I didn't particularly like about the problem statement: the example set that you showed actually two subsets with the desired property: {5, 23} and {13, 9, 3, 3}.

Why did the statement say that "your program should find: 13, 9, 3, 3"?

How could I possibly make a program that is guaranteed to find this subset unless I already knew what the subset was? (Well ---maybe if I wrote a program to find all subsets; then I would be guaranteed to find the one that it really wanted me to find --- yeah! That's the ticket.)

If you run a program organized along the lines that I showed above, you will see that it prints out both sequences. Try it again with different sets and different targets. It prints out every valid subset. Of course it does; that's how it is designed. Is that good or is that bad?

The problem statement isn't clear, but I really don't like being told that the program should find one particular subset without knowing why it shouldn't find another valid one.

So, here's what you could consider:

Add another parameter to the function, a vector of vector of ints (passed by reference). Every time our program finds a valid subset, then, instead of printing it out right then, push it onto the vector of vectors.

Back in the main program, use the size() member function of the vector of vectors to go through a loop that calls a function that prints the members of each valid subset.

Here's the main() program, and I'll stop pretending it's pseudo code. This is the real thing:


The only change to the function pseudo-code is this instead of the place where we previously printed out the subset:


(You, obviously, also change the recursive function call to have the new subsets" parameter.)


My output:


Regards,

Dave

That someone would be me (the OP)
That's why I posted my code - in trying to find a recursive solution to these problems, it sometimes seems like the author is putting the cart before the horse - and I can often see an iterative solution quickly, while the recursive solution is not so intuitive. I'm just trying to understand as completely as possible the "best" way to do things.


I quoted the assignment in its entirety - no, it doesn't say what you are supposed to do with the subset. I had at first thought about just printing the subset, but it seemed to me like it would be more useful to be able to save it for use elsewhere. So that was my extrapolation.


Excellent question! One I will forward to the author, along with the several dozen other errata I have already found in the book.

Do you really need an answer?


Thanks, Dave. Your help is invaluable.

Dave, one more question. In your code the main recursive part is


As a pedantic issue, isn't this technically a combination of an iterative and recursive function? I purposefully avoided any use of for loops in my code thinking that if this were an actual class assignment it'd be a disqualifier.

Just because I specialize in vague generalities doesn't mean that I'll admit to being an expert in pedantics. I have a hard enough time guessing at the answers; I hate it wheh I have to guess at the questions. (In other words what qualifies as recursive is a matter between you and your prof.) See footnote.

My loop is used to get from the beginning of the array to the end. I don't know any easer way. At each step it calls the function recursively. That makes it recursive as far as I am concerned. The bottom line is that it works for me and it was "easy". Your Mileage May Vary.

Regards,

Dave

I had a (very) close friend who was an Electrical Engineering instructor at a large university. The EE Department instituted a policy to require all instructors post last semester's (or last year's) final exams for student perusal. (Fraternities had always kept files of old tests for exclusive use of their members; it seemed more democratic to let everyone have access, and I thought it was a good idea.)

Other instructors worked very hard to make up new tests every semester/year. Comprehensive but all different questions. My "friend" came up with a much easier way: He kept the same questions every time but changed the answers. Problem solved.

Dave, in your main function, what is the reason for evaluating:
? Wouldn't just evaluating
give you the value you need (7 in this case)? What does dividing it by
add to the picture?

No, Why don't you try it? sizeof(set) gives the amount of memory occupied by the array (in bytes).

Dividing by sizeof(set[0]) gives the number of elements declared in the array. (And gives the correct answer for all compilers, regardless of the size of an int.)

By doing it this way I can change the number of items in the initializer list; I can change the array from int to something else; I can change lots of things without touching the line that performs the automatic calculation of the number of elements in the array. (Note that this only works in the context where the array was declared, not in some function with that has that array name as an argument, or anywhere else. The operator sizeof evaluates the expressions at compile time; the results are constants.)




Output on my computer:


Now, try it again for an array of shorts. Try it for an array of longs. Try it for an array of doubles.

Regards,

Dave