22a. Learn Recursion

Review this list once you have learned enough recursion to find discovering patterns and debugging difficult.

• Write a sequence of related examples.

  Related examples mean that the larger ones build off the smaller ones. For example, (f 1234) and (f 123) are related. (f 4321) is not related to the other two.

• Digit patterns should grow in the ones place. See helpful vs. unhelpful in the Common Errors.

• Identify a pattern using concrete cases before converting to an unknown “N”.

  Examples

    (f 5) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2
    (f 6) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2
  

  Find Pattern

    (f 5) = (f 4) + 5^2
    (f 6) = (f 5) + 6^2
    ... ok I get it ...
    (f N) = (f N-1) + N^2
  

• Use mathematical notation, not computer notation, while thinking about your pattern.

Advice

These are common pieces of advice I find myself repeating over and over.

• Have faith that if you put a clear pattern on a paper in front of you, your brain will discover it.

  Human brains are great at finding patterns. Writing related examples helps you see the pattern. Staring at code does not.

• Program only after you have a clear pattern statement. Programming before you see a pattern is guessing, and frustrating.

• The simpler the example, the easier it is to debug.

  When something goes wrong, find the simplest, smallest example and investigate it. For example, if you observe that your grid generator does not work when rows=5 and columns=4, continue to investigate; pehaps you will also discover that it does not work with rows=1 and columns=1 - which is much easier to debug.

Common Errors

• Not arranging number examples in a helpful way. Place value matters. Align digits with the same place value.

  Helpful alignment:

          1
         13
        135
       1357
      13579
  

  Unhelpful alignment:

    1
    13
    135
    1357
    13579
  

• Digit patterns that grow in the left side (“most significant digit”) are more difficult to program than patterns that grow on the right side (“ones digit”).

  Simple pattern: the place value of the new digit is always “ones”.

  N	Pattern
  2	10*N+4
  24	10*N+6
  246	10*N+8
  2468

  Challenging pattern: the place value of the new digit changes: “tens”, “hundreds”, and then “thousands”.

  N	Pattern
  8	N + 60
  68	N + 400
  468	N + 2000
  2468

Memorizing

Some patterns are worth memorizing. Decide if you need to make a study guide and memorize these.

• Get the ones digits of a number.
• Get number which is everything except the ones digit.
• How to reassemble the number 1234 from 123 and 4.