Return to Practical Recursion Home

---

• "If you can’t explain something simply, then you don’t understand it well enough."-Albert Einstein
• "If I had an hour to solve a problem I'd spend 55 minutes thinking about the problem and 5 minutes thinking about solutions." -Albert Einstein

I support the "Drill" method of learning. Drill recursive solutions to many types of problems. In a while, you will recognize the patterns and spot them more easily in new problems.

Many teachers have recently been denouncing the Drill and Kill method of teaching. It means to drill concepts until you kill any desire to learn, and in the meantime, sacrifice any nurturing of creative thinking, problem solving, or analytical skills. To them I say PLEASE! do not diminish the power of Learning through Repetition, and problem solving can also be drilled. Just leave out the ‘Kill’ part.

Definitions

• Recursion 1: Defining a problem in terms of itself.
• Recursion 2: A method where the solution to a problem depends on solutions to smaller instances of the same problem.
• Single Recursion: A function which has one call to itself. e.g. factorial
• Multiple Recursion: A function which has multiple calls to itself. e.g. fibonacci, tree traversals
• Mutual Recursion: indirect recursion where function A calls function B which calls function A...e.g. Minmax algorithm
• Tail recursion: When the last statement of an algorithm restarts the algorithm. ( similar to iterative loops).

Recursion versus Iteration

In most (but certainly not all) situations, iteration is faster and uses less memory. However, recursive code will be shorter , clearer, simpler and more elegant. "To iterate is human, to recurse divine." L. Peter Deutsch

Recursive solutions to problems tend to reveal the structure of the problem itself, thus making it easier to later formulate higher-order abstractions. Iteration tends not to do that. That's one reason to recurse instead of iterate. Recursion imposes a higher cognitive load on the developer than does iterative loops. Recursion is great for directory scanning, but its greatest draw back is that it is memory limited.

The Stack

In programming, recursion works because the computer remembers the previous state of the problem and stores it on the stack (activation stack). For large or complex recursion, humans will quickly lose the ability to trace the stack in their mind, but this is easy for the computer.

The Basic Pattern

Base Case -> Move toward the Base Case -> Recursive call to ourself

We will use this pattern (or similar) when we write our algorithms. Always, Always, Always, start with an algorithm. Then figure out how to code it. Remember "... 55 minutes thinking about the problem..."

Algorithms

Move Mountain(){ If the mountain has been moved, stop. (base case) Else, move one shovel full of the mountain. (move toward base case) Move Mountain() (call ourselves) }

Next up is Induction or Return to home page.

Additional recursion links

Utah University

©2013 deveau enterprises