Scheme For Enlightenment Part Seventeen - C Change

So the next idea is to see what this looks like in C. I've said before that the Scheme version is fast enough. So this exercise is pointless, meaning that it is an exercise.

It's really handy to pass part of the list and use recursion. Can this be done in C without using a linked list library and making copies of lists? Yes. One might use an array, pass a pointer or an index potentially part way into the array, use a handy delimiter so we know when to stop. No need to make copies. The sub lists end at the same place as the full list. Arrays are dumb lists, but are good enough for this sort of thing.

But the recursive structure is still handy, so we'll continue using it.

#include <stdio.h>
#include <stdlib.h>

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  if (am == 0) {
    return 1;
  } else {
    if (am < 0 || c[0] == -1) {
      return 0;
    } else {
      return cc(am - c[0], &c[0]) + cc(am, &c[1]);
    }
  }
}

int main(int argc, char *argv[]) {
  printf("%d\n", cc(atoi(argv[1]), coins));
  return 0;
}

This version works. But i wondered out loud what it might look like using a more Scheme-like syntax. I'm pretty sure no one (sane) would write it this way. The question mark operator isn't very commonly used. Most C programmers think nested comma operators are hard to read. They are. And yet, formulated this way you can still see what is returned fairly quickly. It's whatever is right after a '?', or the last colon.

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  return (am == 0) ? 1 :
    (am < 0 || c[0] == -1) ? 0 :
      cc(am - c[0], &c[0]) +
      cc(am, &c[1]);
}

Again, the original LispMe version for comparison. I'm still trying to wrap my head around how to spot the Scheme return values. As near as i can tell, there's no way around matching the parenthesis for the if operators. The first one is easy. The second one has triple nested parenthesis. And the else clause of the second if starts with addition. The result of the addition is also possibly returned. I was hoping that the Emacs indention would give visual clues. It does. It says that the second if is nested as a clause of the first. It says that the addition operator is a clause of the second if, and the two cc calls are part of the addition. Look sharp for the two constants that are the first clauses of the if's. They seem to just hang there doing nothing. These can be returned.

; count change
(define coins '(50 20 10 5 2 1))

(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))