I am trying to trace this recursive algorithm of the coin change problem with M=10, c={5,3,1} and d=3. M is the value of money for which change is required, c is the different coin values available and d is the number of different coin values available. I am confused as to how to trace it.

**RecursiveChange(M,c,d)**

```
if M = 0
return 0
bestNumCoins <- infinity
for i -> 1 to d
if M ≥ c(i)
numCoins <- RecursiveChange(M – c(i) , c, d)
if numCoins + 1 < bestNumCoins
bestNumCoins <- numCoins + 1
return bestNumCoins
```

Call 1: RecursiveChange(10, {5, 3, 1}, 3)

Call 2: RecursiveChange(5, {5, 3, 1}, 3)

Call 3: RecursiveChange(0, {5, 3, 1}, 3)

In call 3, 0 will be returned since M=0. What I understand: 0 is returned to call 2. Then, continuing from call 2, the following part is run:

```
if numCoins + 1 < bestNumCoins
bestNumCoins <- numCoins + 1
return bestNumCoins
```

where bestNumCoins will take the value of 1. This value of 1 is then returned to call 1. Then, continuing from call 1, since numCoins + 1 (i.e. 2) is not < bestNumCoins (i.e. 1), bestNumCoins will remain 1, and this value of 1 will then be the final value. First of all, I think 2 should be the final value here because to get 10 units, two coins of value 5 are needed.

I need help to figure it out, please. I’ve been spending hours on it.

### More Related Questions

- all solutions to change making with dynamic programming I was reviewing my handouts for our algorithm class and I started to think about this question:
Given different types of coins with different values, find all coin configurations to add […]
- How to avoid StackOverflowError caused by the number of recursion calls in Java? I want to solve this problem: https://www.hackerrank.com/challenges/find-median ,i.e. find the median element in unsorted array. To do this I perform quickselect algorithm. My program […]
- What is the most efficient/elegant way to parse a flat table into a tree? Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' […]
- Determining the complexities given codes Given a snipplet of code, how will you determine the complexities in general. I find myself getting very confused with Big O questions. For example, a very simple question:
for (int i = […]
- Rewriting a recursive function without using recursion I'm rewriting some existing code in a setting where recursive calls are not easily implemented nor desired. (And in Fortran 77, if you must know.) I've thought about making a stack from […]
- What is tail-recursion? Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean? Asked By - Ben Lever Read Answers
- Using trace and dbg in Erlang I am trying to start using erlang:trace/3 and the dbg module to trace the behaviour of a live production system without taking the server down.
The documentation is opaque (to put it […]
- Does sequence contain 5 numbers that are each one apart solved recursively This is the data:
create table #t
(ID int)
insert into #t
values
(-2)
,(-1)
-- ,(0)
,(1)
,(2)
,(3)
,(4)
,(7)
,(5)
[…]
- Getting output from recursion manually in C So, I have two questions.
Question 1) I find recursion difficult in C. And I have this one question, that I dont know how should I go about attempting it. I want to know its output, […]
- How to write trace information to Trace.axd In my asp.net mvc app I want to write trace information for debugging purposes.
For testing only, I used the code below, the only important line for this question is the first […]