# recoursive function

• 01-11-2002
Mecnels
recoursive function
Suppose you've got some money, f.e. 120\$
There are,f.e. 3 different coins, say 1\$, 5\$, and
10\$. The task is to write a program with a recoursive function that calculates how many different ways there are to have 120\$.
F.e. 10 times 10\$ and 4 times 5\$ would be 120\$,
so increase a counter.
The final return value of the recoursive SolveIt()
function is the number of different ways to have a certain amount of money given the number of different coins and their values.
Can you solve this problem (it's difficult), is there an algorithm?
• 01-11-2002
iain
That is 100% a homework question, write some code then post it, at least attempt it.
• 01-11-2002
Nick
This problem isn't too hard.

The number of ways to change an amount with coins 1, 5, 10, 25 is
the number of ways to change the amount with 1, 5, 10 plus the number of ways to change (amount-25) with 1, 5, 10, 25.
• 01-11-2002
Shiro
Perhaps it's recursion where Mecnels is struggling with.

A very easy example of an recursive function:

Code:

```int fac (int n) {     if (n == 1)         return 1;     else         return (n * fac (n -1)); }```
Desiging a recursive function consists of two steps. First there must be an end-step.

n! = n x (n -1) x (n-2) x .. x 2 x 1

You can see, if (n == 1), then the end is reached. In each other case, you have to perform the recursion step. In this example it is easy to see that:

n! = n x (n - 1)!
n! = n x (n - 1) x (n - 2)!

So the recursion step is:

n x (n - 1)!

Or in C:

n x fac (n - 1)
• 01-11-2002
Unregistered
If I remember correctly, the answer is all solutions to this equation.
x + 5y + 10z = 120
0 <= x
0 <= y
0 <= z