Iterative vs. Recursive coding

[John Nagle]

On 8/21/2010 10:08 AM, Michael Torrie wrote:
> On 08/21/2010 03:03 AM, Steven D'Aprano wrote:
>>> - there must be a condition where the recursion has to stop otherwise
>>> the routine will continue to call itself infinitely.
>>>    This is called the Base Case
>>
>> I agree with this, although I've never heard the name "Base Case" before.
>
> "Base Case" is indeed the formal term.  If I recall this term comes from
> inductive mathematical proofs, upon which recursion is based formally.
> In my introduction to computer data structures class we spent a lot of
> time learning about induction and doing inductive proofs.  I always
> hated them until one day when I was trying to teach recursion to a group
> of freshmen and found myself relying on inductive proofs to demonstrate
> that recursion indeed works.  For the uninitiated, recursion is often
> thought about too deeply.

    If you want to think about it deeply, read Abelson and Sussman.
(http://mitpress.mit.edu/sicp/).

    Realistically, recursion isn't that important in Python.  It's
there if you need it, and sometimes useful, but generally not used
much without good reason.  In some functional languages, recursion
is routinely used in place of iteration, but Python isn't built for
that.  In Python, most of the use cases for trivial recursion
are better handled with iteration or generators.

				John Nagle