In count change recursive algorithm, why do we return 1 if the amount = 0?

Question

I am taking coursera course and,for an assignment, I have written a code to count the change of an amount given a list of denominations. A doing a lot of research, I found explanations of various algorithms. In the recursive implementation, one of the base cases is if the amount money is 0 then the count is 1. I don't understand why but this is the only way the code works. I feel that is the amount is 0 then there is no way to make change for it and I should throw an exception. The code look like:

function countChange(amount : Int, denoms :List[Int]) : Int = {
  if (amount == 0 ) return 1 ....

Any explanation is much appreciated.

Answer 1

To avoid speaking specifically about the Coursera problem, I'll refer to a simpler but similar problem.

How many outcomes are there for 2 coin flips? 4.

(H,H),(H,T),(T,H),(T,T)

How many outcomes are there for 1 coin flip? 2.

(H),(T)

How many outcomes are there for 0 coin flips? 1.

()

Expressing this recursively, how many outcomes are there for N coin flips? Let's call it f(N) where

f(N) = 2 * f(N - 1), for N > 0
f(0) = 1

The N = 0 trivial (base) case is chosen so that the non-trivial cases, defined recursively, work out correctly. Since we're doing multiplication in this example and the identity element for multiplication is 1, it makes sense to choose that as the base case.

Alternatively, you could argue from combinatorics: n choose 0 = 1, 0! = 1, etc.