Versions Compared

Old Version 11

changes.mady.by.user Robert Cartwright

Saved on

compared with

New Version 12

changes.mady.by.user Robert Cartwright

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

If the template does not guarantee that a function terminates, you are required to explain why that function will terminate for all possible inputs.  The standard structural recursion templates guarantee termination.  All instantiations of basic data definition templates are guaranteed to terminate.

  • Example 7. Termination argument for quick-sort :

    Code Block
          ;; quick-sort list-of-number -> list-of-number
      ;; Purpose: (quick-sort lon) sorts lon into ascending order
      ;;
      ;; Examples:
      (check-expect (quick-sort empty) empty)
      (check-expect (quick-sort '(1)) '(1))
      (check-expect (quick-sort '(1 4 3 5)) '(1 3 4 5))
      (check-expect '(1 4 3 4 2 5)) '(1 2 3 4 4 5))
      ;;
      ;; Termination:
      ;; On each call, quick-sort partitions the list alon into three sublists using
      ;; smaller-than, larger-than, and equal-to.  The lists produced by smaller-than
      ;; and larger-than are sorted using recursive applications of quick-sort. Since
      ;; the lists produced by smaller-than and larger-than are strictly shorter than
      ;; alon (the given list), quick-sort terminates.
      (define (quick-sort alon)
        (cond
          [(empty? alon) empty]
          [else (append (quick-sort (smaller-items alon (first alon)))
                        (equal-to alon (first alon))
                        (quick-sort (larger-items alon (first alon))))]))

      ;; Remainder of this example (including the definitions of smaller-items and larger-items) is elided
      ...