[Tutor] Recursive Least Common Multiple

[Danny Yoo]

On Tue, 17 Jul 2001, Timothy M. Brauch wrote:

> I would like to break up a number into its addition parts.  For
> example, with the number 7, I need a list returned like:

> [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[1,1,5],
>  [1,2,4],[1,3,3],[1,4,2],[1,5,1],...
>  [2,1,1,1,1,1],[1,1,1,1,1,1,1]]

> I really feel like my code could be a lot shorter if I knew some
> trick, and some other trick would actually do what I need.  Any help
> would be greatly appreciated.  Also, I created the dummy variable so
> as not to destroy n in case I need to use it later.

Your question sounds really similar to a somewhat involved problem in
computer science called the "change-making" problem.  The change-making
problem asks us to give all possible ways of turning some about of money
into a pocketful of change, if we're restricted to use quarters, nickles,
dimes, and pennies.

Your problem is a variant because it allows any denomination, even
imaginary ones like ookles, limes, warters, and dennies.  You also hit
upon the key phrase for the solution: "recursive": there's a great
recursive solution that's relatively short, beautiful, and utterly
inefficient.  *grin* (This is also a great way to introduce another CS
idea called "dynamic programming", but let's talk about it later.)

A simple example might help introduce the recursive idea.  Let's say that
we're trying to make all ways of making 15 cents in change, and we have an
unlimited number of nickles, dimes, and pennies.  One thing we can do is
to set aside a dime, and try to find all ways of making 5 cents in change.  
Or we could set aside a nickle, and make 10 cents in change.  Or we could
set aside a penny, and try to make 14 cents of change.

Since we have three smaller, but similar problems, we apply the same sort
of reduction.  Think about it for a while, and try it out.  It's a fun
program to write.


Good luck!