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.

Answer 1

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.