About the speed:

I added a counter to check how many times it went through the inner loop:

count_change(100) = 292: with 606 steps

count_change(200) = 2435: with 1206 steps

count_change(300) = 9590: with 1806 steps

...

count_change(1000) = 801451: with 6006 steps

You can see it's going up linearly

That's the dynamic programming approach.

A similar technique is memoization which lends itself very nicely to the way the original problem is given in scheme. I'll use racket:

Adding a count to the program given in SICP

    #lang racket
    (define steps 0)
    (define (count-change amount)
      (cc amount 5))
    
    (define (cc amount kinds-of-coins)
      (set! steps (add1 steps))
      (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)))

(count-change 100): 292 in 15499 steps

(count-change 200): 2435 in 229589 steps

(count-change 300): 9590 in 1292591 steps

Yeah - I'm not even going to try (count-change 1000)

This is the problem with tree recursion :(

Converting to a memoized version (I'm cheating by using a library that gives define/memo but it's evasy enough to write a memoized version of a function.

    (require memoize)
    (define (count-change amount)
      (cc/memo amount 5))

    (define/memo (cc/memo amount kinds-of-coins)
      (set! steps (add1 steps))
      (cond ((= amount 0) 1)
            ((or (< amount 0) (= kinds-of-coins 0)) 0)
            (else (+ (cc/memo amount
                         (- kinds-of-coins 1))
                     (cc/memo (- amount
                            (first-denomination kinds-of-coins))
                         kinds-of-coins)))))

(count-change 100): 292 in 250 steps

(count-change 200): 2435 in 496 steps

(count-change 300): 9590 in 742 steps

(count-change 1000): 801451 in 2464 steps

That's even less steps than using dynamic programming although it probably uses a little extra memory to store teh memoized values.