Recursion

Intuition:

Some problems can most naturally be represented recursively. Note that any problem that can be represented recursively can also be done non-recursively. The non-recursive versions will often be computationally faster, though often not as easy to understand.

1. Looking into a mirror reflected in a mirror, or recursive screenshots [idea from Brian Cichoracki]

2. Escher's hands drawing each other,

3. Bach's music, for instance this segment (or on Spotify) (1.4MB) from Contrapunctus I, played by Gould (excerpted from the site for a course at Stanford. Also check out the images on that site.) See a Google Doodle example harmonizing the melody "Twinkle Twinkle Little Star" encompassing both the ideas of Bach and AI [Thanks to Jakob Eriksson]

4. See examples of the layout of an African Ba-ila settlement.

5. Recursive smile video

6. Stephen Hawking's 1988 book A Brief History of Time starts: "A well-known scientist (some say it was Bertrand Russell)... turtles all the way down...

7. Line up people, all blindfolded, in a column, where the front-most person is next to the wall. Have the person at the back ask the person in front of them "How far am I from the wall?" That person in turn asks the next, and so forth. Finally the person who is next to the wall returns the answer "one", and that person returns "two," and so forth back to the original person who asked the question.

8. Video of the Algorithm March with Ninjas, or the world-record version with prisoners in the Philippines.

9. See the YouTube video of "Dueling Carls" [Thanks to Brent Sonin]

10. Clapping Game (originally from http://www.can.ibm.com/k12/scitechmatics/recursion.html )

    1. Regular version: When I clap, Raise your hand once.

    2. Recursive version: whenever you hear someone clap, raise your hand once and then clap

    3. What is the base condition? When does it stop? How could we make it stop?

11. Typing in a search for the word recursion in Google asks "Did you mean recursion?" [Thanks to Zach Quinn]

12. Other:

    1. Fractals images, where the image in the large is repeated in the small. The Hilbert Curve can also be seen in 3D.

    2. Chess (if I move and then you move and then I move...)

    3. The segments of the shell of a Chambered Nautilus

    4. Nested Matryoshka dolls

Factorial Example

• 1. Non-recursive version of factorial:

// Find the factorial of a non-negative integer x

int factorial( int x) {

int answer = 1;

for (int i=x; i>0; i--) {

answer = answer * i;

}

return answer;

}

• 2. Recursive version of factorial: Two trace approaches are illustrated in this Word document as follows:

     1. 1. Write as multiple functions with different names, calling each other

        2. Write in outline form (compress the function body to make this easier to write)

  3. Other examples, which include:

• • • 1. Reversing digits in a number:

         1. A non-recursive method printReverse( ) that takes an input number and displays its digits in reverse order.

         2. The same thing done recursively in method recursivePrintReverse( ), which prints on the way in to the recursion ("head" recursion)

      2. Reversing text in method reverseText() by printing on the way back out of the recursive calls ("tail" recursion).

      3. Misc examples (methods f1( ) through f4( ), some of which implement various mathematical operators. Can you figure out what they do?

The Maze program

Consider the maze problem, where there is a rabbit in a maze. The maze is represented as a one-dimensional array. There are several different versions of the solution:

maze1 shows how to make moves and how recursion explores all possible paths. The program gives a message once it reaches the destination, but it doesn't stop recursing, nor does it print a solution.

maze2 shows the solution path, though it is in reverse order.

maze3 How might we use recursion to give the solution path in order?

maze4 showing the effect of introducing a loop

maze5 various possible attempts to display the solution path in order