Recursion & Induction

A username and password may be required for some online papers. Please contact Bill Rapaport.

1. Falling-domino movies:
   1. "Falling Dominos! #2"
   2. "Beer Bottle Dominos"
   3. "Greatest Pool Shot"
   4. Fall of the Berlin Wall
   5. 
      Review of Things to Make and Do in the Fourth Dimension
      • Includes a video showing how logic gates and a binary adder can be built using falling dominoes.
        

   ---

2. Hayes, Brian (2006), "Gauss's Day of Reckoning", American Scientist 94(3) (May-June): 200ff.
   • The truth behind the legend of Gauss's discovery that Σ(i ∈ {1,...,n})[i] = n(n-1)/2.

   ---

3. A Recursive Definition of Strings

   ---

4. On Fibonacci numbers:

   1. Hoffer, William (1975), "A Magic Ratio Recurs throughout Art and Nature", Smithsonian (December): 111–112, 115–118, 120, 123–124.

   2. Preiss, Bruno R. (1998), "Fibonacci Numbers" (in Java)
      • from Preiss, Bruno R. (1999), Data Structures and Algorithms with Object-Oriented Design Patterns in Java (Hoboken, NJ: John Wiley & Sons).

   3. Hayes, Brian (1999), "The Vibonacci Numbers" [sic], American Scientist 87 (July-August): 296–301.

   4. "Dr. Steel's Fibonacci Sequence"
      • Animated music video

   ---

5. Buck, R.C. (1963), "Mathematical Induction and Recursive Definitions", American Mathematical Monthly 70(2) (February): 128-135.

6. Gardner, Martin (1971), "Infinite Regress", Ch. 22 of Martin Gardner's Sixth Book of Mathematical Games from Scientific American (San Francisco: W.H. Freeman): 220-229.

7. Hofstadter, Douglas R. (1985), 2 chapters on recursion and a preliminary chapter on Lisp, from Metamagical Themas: Questing for the Essence of Mind and Pattern (New York: Basic Books):
   • Ch. 17: Lisp: Atoms and Lists, pp. 396-409
   • Ch. 18: Lisp: Lists and Recursion, pp. 410-424
   • Ch. 19: Lisp: Recursion and Generality, pp. 425-454.

8. Dewdney, A.K. (1989), 2 chapters on recursion from The Turing Omnibus: 61 Excursions in Computer Science (Rockville, MD: Computer Science Press):
   • Ch. 21: Recursion: The Sierpinski Curve, pp. 139-146
   • Ch. 51: Iteration and Recursion: The Towers of Hanoi, pp. 332-336.

9. Allen, Lucas G. (2001), "Teaching Mathematical Induction: An Alternative Approach", Mathematics Teacher 94(6) (September): 500-504.

   ---

10. On Peano and his axioms:

    1. Joyce, D. (2005), "The Dedekind/Peano Axioms".

    2. Kennedy, Hubert C. (1968), "Giuseppe Peano at the University of Turin", Mathematics Teacher (November): 703–706; reprinted in Kennedy, Hubert C. (2002), Twelve Articles on Giuseppe Peano (San Francisco: Peremptory Publications): 14–19.

    3. "Giuseppe Peano", Wikipedia.

    ---

11. Corballis, Michael (2007), "The Uniqueness of Human Recursive Thinking" American Scientist 95(3) (May-June): 240ff.

12. Odifreddi, Piergiorgio (2007), "Recursive Functions", in Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy (Summer 2007 Edition).
    • See also:
      Rapaport, William J. (2007), "What Is Computation?"

13. Spector, Lawrence (2008), "Mathematical Induction", from The Math Page
    • A clever, interactive intro to mathematical induction.

14. Weisstein, Eric W. (2008), "Recursion", from MathWorld—A Wolfram Web Resource.

15. Wu, Hung-Hsi (2009), "What's Sophisticated about Elementary Mathematics?", American Educator 33(3) (Fall): 4–14.
    • "All whole number computations are nothing but a sequence of single-digit computations artfully put together.
      This is the kind of thinking students will need to succeed in algebra and advanced mathematics."
    • That kind of thinking is called "recursion"!

    ---

16. Definitions & Examples of Recursion:

    1. Recursion, from Everything2.com
       • Contains humorous definitions and examples of recursion...

       • …one of which reminded me of the best recursive movie: Passage to Marseilles (1944), starring Humphrey Bogart and most of the cast of Casablanca.
         It begins with a reporter asking a character (played by Claude Rains) who the Humphrey Bogart character (Matrac) is.
         In a flashback, the Rains character tells how he met Matrac.
         Part of his story involves a flashback of someone else telling a story,
         part of which is a flashback of someone else telling a story,
         …,
         until all the stories flash forward
         (or "unwind", as computer scientists say),
         and we're back in the present.

    2. Here are a couple more humorous definitions; these are from the Wikipedia article on recursion:
       • "Here is another, perhaps simpler way to understand recursive processes:
         1. Are we done yet? If so, return the results. Without such a termination condition a recursion would go on forever.
         2. If not, simplify the problem, solve the simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution.

       • A more humorous illustration goes: ‘In order to understand recursion, one must first understand recursion.’

       • Or perhaps more accurate is the following, from Andrew Plotkin: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."

    3. Or you could try Googling "recursion" and then noticing what Google's "correction" ("Did you mean...") is.

    4. On the need for a base case:

       

       (The mathematician Leopold Kronecker once said: "The dear God made the whole numbers; all else is man-made.")

    ---

17. On Recurrence Relations:
    1. On their relationship to difference equations, see: "Relationship to difference equations", in "Recurrence relation", Wikipedia (accessed 13 January 2009).

    2. "...theoretical physicists commonly describe the world using differential equations, which specify the rate of change of physical variables, such as density, at each point in the spacetime continuum. But when spacetime is grainy, we instead use so-called difference equations, which break up the continuum into discrete intervals."
       —Bojowald, Martin (2008), "Follow the Bouncing Universe", Scientific American (October): 44-51; quote on p.47 (emphasis added).
       • "continuum" = a mathematical entity that is continuous, i.e., not discrete;
       • "grainy" = "gappy", discrete

    3. Rapaport, William J. (1974), "Paper Folding and Convergent Sequences", Mathematics Teacher 67 (May): 453-457.
       • Discusses an interesting sequence that can be constructed by folding a strip of paper and that converges to a surprising number.
       • The article gives a solution using ideas from calculus, but can also be done using recurrence relations.
       • (My very first publication, too! :-)

    4. "How to Generate the Thue Morse Sequence", WikiHow
       • Presents a curious binary sequence that can be defined using recurrence relations; also, has some interesting links.