You're right imo.
Thats somehow what I wanted to express with my statement, that there's no way a recursive solution could simplify the complexity of the problem domain.
You can only code a recursive solution, which evaluates the same possibilities as the nested loops.

I think you're misunderstanding the recursive solution if you think it's evaluating the same possibilities as the nested loops.

Unless I'm misreading your code (possible, but unlikely), you're doing a selective dictionary attack on the problem -- that is, try all possible combinations of change and keep the ones that get you the total amount that you want. Which means that although you can set upper and lower bounds to the total amount, you're still considering combinations that Just Don't Work. (i.e. some combinations get you $2 when you want $1.50)


Notice that at the highest values of i, j, k, and l here, you are considering a combination that cannot possibly be correct. In the if block, you are quite literally testing

at the end of the loop here.

The inductive solution explicitly does NOT do that or anything like it. Instead, it is a generator -- it generates all the possible combinations that satisfy the problem space to an exact amount, with no extra work being done or thrown away. At any given step of the process, the recursive solution is in the process of building a bona fide, 100% valid combination.

The fact that the recursive code creates duplicate copies of the same solutions is a fault of the code, not the solution (because from the perspective of readability and simplicity of expression, deduping is easier than implementing the inductive solution verbatim). It's worth noting that by definition, whatever extra work is done (i.e. generating duplicates) still results in generating solutions that are valid and not invalid ones that you test and throw away.

Or here's another way to look at it. The recursive implementation is doing a full BFS over the solution itself (and sometimes revisiting the same node twice or more than twice). The iterative implementation is (generously speaking) doing a bounded BFS over the solution space.

So you are either seriously misunderstanding the code you wrote for yourself, or you are seriously misunderstanding what the inductive/recursive solution actually does.

This post was edited by irimi on Dec 5 2012 01:46pm

If it would be possible to test only the solutions which are valid, it would not be necessary to test any solutions at all... Because those are already valid, as you said. So when you know which combinations to test, you already know the solution...

In other words (but same meaning):
Your "wonder" algorithm needs to know which solutions are valid, so that he only tests those. But why testing those? Those are valid... The real problem is finding the solution space

Imo your arguments are completely invalid xD

For visualisation of your logic (As I still understand it, after honestly thinking about the problem):
Think about an algorithm for finding prime numbers between 2 and 100.
Let the algorithm be testing if it has only 2 dividers. Of course this is just a brute-force.
(There are also improved algorithms which reduces the amount of tests, but still it has to test false numbers. But we don't want to talk about those algorithms here.)
Now you come and tell me, that there could be an algorithm, which only tests the numbers of the solution space...
You see what I want to tell you?
To let your algorithm test only valid solutions, you had to know which are valid... But the problem is finding the valid solutions

e: double post

This post was edited by irimi on Dec 8 2012 09:59am

now you just sound like you don't know how induction actually works. notice how you're completely ignoring and/or failing to address any of the points brought up in the previous post, and instead trying to argue against something i didn't even bring up. bringing up a different problem that lends itself to using a different solution/approach isn't actually valid when we're talking about something pretty specific here.

hell, i'll even humor your example and point out why induction works for this problem (and why it won't work for yours) -- in this problem, we are building combinations of things, and we know exactly what all the partial solutions are supposed to look like, without testing them, because you can be generating legitimate answers to smaller versions of the problem at each step of the way (which is the cornerstone of inductive solutions -- reduce the problem to smaller problems until you get to the fairly trivialized base case, and then bootstrap back into the other direction). so it follows then that the problem boils to down (as carteblanche pointed out) one of generation, and nothing else, whereas in the prime number example, knowing the last prime number doesn't give you any knowledge of what the next prime number is going to be. the reason that the iterative approach is brute force is in part because it throws away that knowledge and does a simple iterate-and-test.

this isn't an argument of opinion, by the way. it's one based on fact. you can't just say, "Your solution guesses on the same amount of possibilities" and call that opinion.

This post was edited by irimi on Dec 8 2012 10:11am