Pseudo code into logical steps?

Question

I am trying to solve the coin-change problem:

Given a list of number , k , how many ways are there to give change to a given amount m.

As one of the resource I have the following pseudo code:

 (define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

However I don't understand this pseudo code. It has the arithmetic signs in front when they should be behind. I understand up to the point where the else statement starts. But when going inside the else loop I have no idea what is going on. Can you please reduce this pseudo code to a number of logical things to do at each step after the else clause?

Or what article would be more useful that this pseudo code to solve this problem. Googling this I only find problems that ask you to give the optimal change however I don't need that.

NOTE Please do not give me the code as this is a coursera course and a direct answer would violate the honour code.

UPDATE As @EmilVikström kindly explained to me what exactly is going on in there I have tried to produce a small pseudo-code that should be the same as the scheme ( This is only the else clause as the rest is pretty self-explanatory even to me).

else
  cc ( amount - kindOfCoins.head , kindOfCoins) + cc ( amount , kindOfCoins.tail )

Is this the thing that results from scheme? If not where did I go wrong? Please yet again do not give me the answer ( Just point me in the right direction if you could) as this will violate the coursera honour code.

This looks like Scheme code. The "arithmetic signs in front" just means "apply the `+` function to these two arguments". — Emil Vikström, May 07 '14 at 07:21
It is Scheme. And yes, it has the arithmetic signs in front. If the teachers want you to understand Scheme, they should have pointed you to some tutorial or other. Effectively, you *have* the code and you're asking us to un-code it. — Fred Foo, May 07 '14 at 07:23
@EmilVikström What about the - sign in the return clause where cc is called again ? I can deduce from what you said that cc is aplied to the amount plus something. Which I think is a list. However it would make sense I believe is the list is not complete. If the list has all elements but the first one. Is this the case? One final thing. Is the return clause an addition of the two cc functions? — Bula, May 07 '14 at 14:34

score 1 · Answer 1 · answered May 07 '14 at 15:42

This is the contents of the else block:

(+ (cc amount
       (- kinds-of-coins 1))
   (cc (- amount
          (first-denomination kinds-of-coins))
       kinds-of-coins))

This is Scheme where all functions, including arithmetic operations, is a parenthesis with the function name as first element and the arguments to the function as elements afterwards.

First you have a call to the + function with two arguments. Let's call the arguments a and b for the purposes of this explanation:

(+ a b)

Both a and b happen to be function calls. Here is a:

(cc amount (- kinds-of-coins 1))

and b:

(cc (- amount ((first-denomination kinds-of-coins)) kinds-of-coins)

Let us focus on the first of them, a. a is a function call to cc with two arguments, let's call them x and y, and we have this function call: (cc x y) where x = amount and y = (- kinds-of-coins 1). So you see that y is also a function call.

And this goes on. You can look at each parenthesis in itself and resolve it's value. Start from the inner-most parenthesis (as in mathematics) and work your way outwards.

You also need to understand that cc is recursive, which means that it calls itself to do its work. It will eventually stop calling itself, when the code doesn't enter the else block anymore due to the other conditions being true. This stop condition is called the base case of the recursion. A good recursive function will always get closer to its base case in each recursive step (each time it calls itself), so you can be sure that it will eventually reach it.

Thank you for your explanation. I tried to decipher the scheme from the else clause. Could you please tell me if I got it right? I appreciate your help ( check updates ) — Bula, May 07 '14 at 18:48

Pseudo code into logical steps?

1 Answers1