<jupyter_start><jupyter_text>Exercise 1.14.  Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?<jupyter_code>(define (count-change amount)
  (cc amount 5 ""))
(define (cc amount kinds-of-coins spacer)
  (display (format "~acc ~a ~a\n" spacer amount kinds-of-coins))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1) (format " |~a" spacer))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins (format " |~a" spacer))))))
(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 11)<jupyter_output>cc 11 5
 |cc 11 4
 | |cc 11 3
 | | |cc 11 2
 | | | |cc 11 1
 | | | | |cc 11 0
 | | | | |cc 10 1
 | | | | | |cc 10 0
 | | | | | |cc 9 1
 | | | | | | |cc 9 0
 | | | | | | |cc 8 1
 | | | | | | | |cc 8 0
 | | | | | | | |cc 7 1
 | | | | | | | | |cc 7 0
 | | | | | | | | |cc 6 1
 | | | | | | | | | |cc 6 0
 | | | | | | | | | |cc 5 1
 | | | | | | | | | | |cc 5 0
 | | | | | | | | | | |cc 4 1
 | | | | | | | | | | | |cc 4 0
 | | | | | | | | | | | |cc 3 1
 | | | | | | | | | | | | |cc 3 0
 | | | | | | | | | | | | |cc 2 1
 | | | | | | | | | | | | | |cc 2 0
 | | | | | | | | | | | | | |cc 1 1
 | | | | | | | | | | | | | | |cc 1 0
 | | | | | | | | | | | | | | |cc 0 1
 | | | |cc 6 2
 | | | | |cc 6 1
 | | | | | |cc 6 0
 | | | | | |cc 5 1
 | | | | | | |cc 5 0
 | | | | | | |cc 4 1
 | | | | | | | |cc 4 0
 | | | | | | | |cc 3 1
 | | | | | | | | |cc 3 0
 | | | | | | | | |cc 2 1
 | | | | | | | | | |cc 2 0
 | | | | | | | | | |cc 1 1
 | | | | | | | | | | |cc 1 0
 | | | | | | | | | | |cc 0 1
 | | | | |cc 1 2
 | | |[...]
{'fraction_non_alphanumeric': 0.24352078239608801, 'fraction_numerical': 0.05965770171149144, 'mean_word_length': 1.6163682864450128, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '221132', 'license': 'CC0-1.0', 'n_tokens_mistral': 988, 'n_tokens_neox': 841, 'n_words': 236, 'path': 'ch1/1.2/ex.1.14.ipynb', 'repo_name': 'for-tokyo/sicp', 'size': '2045'}