StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Recursion is a design technique based on inductive proofs. Considers one or more base (simple) case(s) for your problem, and one or more ways to move the problem closer to being a base-case problem. Then, at each step of the algorithm, you either recognize completion (and deal appropriately with a base case) make the problem slightly closer to being a base case.</p> <p>Bubble sort is just an application of the observation that a sorted array has all adjacent pairs of elements in order. Defined recursively, it works like:</p> <ol> <li>Base case: There's an array of size 1 (or less) to sort. It's sorted, of course.</li> <li>Inductive case: Bubble the largest element to the top of the array. Now there's a one-element smaller array to sort, which do.</li> </ol> <p>You can write that very idea in the programming language of your choice, and you get bubble sort. Oh, but you have to define what it means to "bubble the largest element". Well, that's another opportunity for recursive design. I think you get the idea, though.</p> <p>Faster sorts are mostly based on observations about how you get closer to the goal in less work. Quick sort, for instance, relies on the notion that, if an array is sorted, then there is some element P, and all elements less than P are to P's left, and all elements more than P are to P's right. If you can establish that property on an array, and also pick P, then you can cut the problem roughly in half at each step instead of simply by one.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload