D.4.2

Describe the application of recursive algorithms.

*Teaching Note:*

Students should understand that recursion can be applied to a small subset of programming problems to produce elegant solutions. Students should also understand that recursive algorithms are rarely used in practice.

LINK Thinking abstractly, thinking recursively.

Sample Question:

sdfsdfsf

JSR Notes:

The two teaching notes are key here.

And note, as noted elsewhere, that you should never use recursion for the sake of using recursion - to be fancy. Because recursion takes tons of system resources, since instance after instance after instance of a particular method is called, leading to potentially large stacks of un-finished recursive calls.

Usually when recursion is used it is used because there is no other (or no other straight-forward) iterative way of solving the problem.

(If not having had looked at the Towers of Hanoi or fractals examples, you should do so now, just to have a general idea of how they work.)

Examples we have seen so far:

- Recursive binary search

- Traversals through trees (pre-order, post-order, in-order)

Note that recursion is rare, but the only straight-forward way to represent certain (recursive) situations.