Iterative vs. Recursive coding

[Thomas Jollans]

- every time the procedure calls itself the memory gradually fills up
with the copies until the whole thing winds down again
as the "return" statements start being executed.
- the above point means that a recursive approach is expensive on
resources so in the practical world it should be avoided.
(Thanks John for giving me a real life example where recursion is
recommended)

This is only partly true. In most programming languages "typical" today, this
is true: each recursion is a normal function call which allocates space on the
stack. Thus, the maximum recursion depth is severely limited.

However, in most functional programming languages, recursion is recognized as
a highly expressive, powerful, and idiomatic tool that can often be optimized.
Languages like haskell or scheme compile tail-end recursive functions in a
manner that is just as efficient as a loop would have been. In general, if you
could rewrite a recursive scheme function to use a loop, then a decent scheme
compiler will be able to "do it for you" behind the scenes.

 

[Martin Gregorie]

For the purposes of learning programming i think it's a must to
understand Recursion so thanks all for your help!

That depends on the language and/or hardware. COBOL wouldn't understand
recursion if hit on the head with a recursion brick and early computer
hardware (those without a stack) made it VERY hard work. If you don't
follow this, look at the CODASYL language specification for COBOL or the
hardware design of ICL 1900 or IBM System/360 mainframes (which are still
the heart of the financial world) and work out how to implement a
recursive function for any of them. Its not easy but it can be done.

Ok so now i hope you all agree that my code is also correct

Yes: it runs and does what I'd expect. A good result.

A basic skill for a programmer is to understand the specification for a
piece of code and write test cases. This is a set of inputs (both
expected/sensible and totally out of order) and the expected outputs from
each set of inputs. Then you write the code and run it against the test
cases to show that it does what the specification requires.

Never bullshit yourself or anybody else about this conformance to spec:
either you screwed up or, hopefully less often, the designer wrote an
ambiguous or plain wrong requirement. Either way, the problem must be
resolved and the code be made to do what is wanted.

while (results don't match the spec):
Rince, wash, repeat.

 

[John Nagle]

I think you mean tail recursion optimization / elimination.
Python does tail recursion:

Not very well.

def cnt(n) :
if n > 0 :
cnt(n-1)


This will work for up to cnt(998), but at cnt(999), CPython
reports "RuntimeError: maximum recursion depth exceeded."

Yes, you can increase the recursion depth, but that case
shouldn't be compiled to recursion at all.

John Nagle

 

[Steven D'Aprano]

Is this a sincere surprise or are you just boasting?

Why would it be boasting? I didn't say that at the age of seven I
independently invented a COBOL compiler that supported recursion. *That*
would be boasting. (It would also be a lie -- at the age of seven, I
don't think I even knew about the existence of computers.)

Boasting about understanding the idea of recursion is kind of like
boasting about the putting my hands in the correct glove nine times out
of ten.


[...]

The fact, that you didn't have the issue doens't mean it's easy for
others.

Apparently not.

 

[Steven D'Aprano]

Steven D'Aprano a écrit :
I onced worked in a shop (Win32 desktop / accouting applications mainly)
where I was the only guy that could actually understand recursion. FWIW,
I also was the only guy around that understood "hairy" (lol) concepts
like callback functions, FSM,

FSM? Flying Spaghetti Monster?

polymorphism, hashtables, linked lists,
ADTs, algorithm complexity etc...

Was there anything they *did* understand, or did they just bang on the
keyboard at random until the code compiled? *wink*

Needless to say, I didn't last long !-)

And rightly so

 

[Steven D'Aprano]

For future readers of this post who want to learn to programm (just like
myself) let me re-state the basics i have learned now:

I would disagree in part with nearly all of these.

- a procedure is said to be recursive when it contains a statement that
calls itself

Not necessarily.

A function can be indirectly recursive -- function f can call function g
which calls function h which calls function f. This is still recursion,
even though f doesn't contain a statement which calls itself.

- 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.

- every time the procedure calls itself the memory gradually fills up
with the copies until the whole thing winds down again
as the "return" statements start being executed.

That's so vague as to be almost meaningless. I think what you are talking
about is one specific part of memory, the calling stack, which fills up
with arguments needed to call the function, and then empties as the
recursive calls return.

However, there is an import class of recursive calls where a sufficiently
smart compiler can avoid this cost, essentially turning recursion into
iteration automatically, speeding up recursion drastically.

- the above point means that a recursive approach is expensive on
resources so in the practical world it should be avoided.

True-ish for the first part of the sentence, absolutely false for the
second.

Recursion can be slower and more memory consuming than iteration under
some circumstances, although this depends on the specific way that
recursion is used, not the mere fact that recursion happens. A single
recursive call is no more expensive than any other function call.

Also, as mentioned, some compilers can optimize tail-call recursion to
make it as fast and efficient as iteration. (However, Python doesn't do
this.)

In the real world, avoiding recursion also has costs. Your function may
be bigger, more complicated, need more memory, possibly manage its own
stack. None of these things happen for free. Whether a specific recursive
function is better than a specific iterative function depends on the
details of what that function does and what arguments you call it with.

If your recursive function is likely to use only a few recursive calls,
there is no need to complicate matters by re-writing it iteratively.
There's no need to avoid recursion just because it is recursive.

Also, recursion together with memoisation can be extremely fast and
efficient, at some cost of memory. For example, the typical recursive
version of factorisation:

def fact(n):
if n <= 1: return 1
return n*fact(n-1)

can be made much, much faster by giving it a simple cache:

def fact(n):
try:
cache = fact.cache
except AttributeError:
cache = fact.cache = {}
try:
return cache[n]
except KeyError:
pass
if n <= 1:
result = 1
else:
result = n*fact(n-1)
# Don't let the cache grow indefinitely large.
if len(cache) >= 100:
cache.popitem() # Discard some arbitrary item.
cache[n] = result
return result

 

[Baba]

On 8/20/2010 1:17 PM, John Bokma wrote:

    Not very well.

     def cnt(n) :
         if n > 0 :
             cnt(n-1)

Hi John

I'm intrigued by this example. Is there something missing in the code?
When i run it i get: <function cnt at 0x02B2FE70>
I suppose it is meant to print a sequence of numbers from n down to
zero?

re tail recursion, on wiki i found:
"With tail recursion, there is no need to remember the place we are
calling from—instead, we can leave the stack alone, and the newly
called function will return its result directly to the original
caller. Converting a call to a branch or jump in such a case is called
a tail call optimization. "

not sure i understand that...
is this bit of theory applicable to your cnt function above?

tnx
Baba

 

[Tim Chase]

I'm intrigued by this example. Is there something missing in the code?
When i run it i get:<function cnt at 0x02B2FE70>
I suppose it is meant to print a sequence of numbers from n down to
zero?

Sounds like you merely executed:
<function cnt at 0xDEADBEEF>

which just asks what "cnt" is (in this case, it is as Python
reports: a function named "cnt" at some given address), instead
of actually *running* the function:

(function-calling is performed by the parens).

re tail recursion, on wiki i found:
"With tail recursion, there is no need to remember the place we are
calling from—instead, we can leave the stack alone, and the newly
called function will return its result directly to the original
caller. Converting a call to a branch or jump in such a case is called
a tail call optimization. "

not sure i understand that...
is this bit of theory applicable to your cnt function above?

The recursive call (calling cnt(...) again) is the last
instruction in the function before it would otherwise exit. A
tail-recursion-aware compiler/interpreter would optimize that
away. Instead of keeping track of a new stack-frame for each
call (growing in stack-memory usage with each call), it would
recognize that it could just reuse the current/top stack-frame to
prevent stack blowouts.

JohnN's observation was that Python doesn't recognize
tail-recursion, and thus blows the top of the default stack-size
at 999 recursive calls (a number adjustable with parameters to
Python). If Python recognized tail-recursion and optimized for
it, you could use any number you had the time to wait for.

-tkc

 

[Tim Chase]

FSM? Flying Spaghetti Monster?

I'm guessing "Finite State Machines". But in a way, "Flying
Spaghetti Monster" is also a bit "hairy" and hard to understand...

Was there anything they *did* understand, or did they just bang on the
keyboard at random until the code compiled? *wink*

Accompanied by coping and pasting example code from Google
results, random twiddling of the code or posting questions on
newsgroups until the code compiles...a surprisingly popular
technique. :-(

-tkc

 

[Dave Angel]

Hi John

I'm intrigued by this example. Is there something missing in the code?
When i run it i get: <function cnt at 0x02B2FE70>
I suppose it is meant to print a sequence of numbers from n down to
zero?

re tail recursion, on wiki i found:
"With tail recursion, there is no need to remember the place we are
calling from—instead, we can leave the stack alone, and the newly
called function will return its result directly to the original
caller. Converting a call to a branch or jump in such a case is called
a tail call optimization. "

not sure i understand that...
is this bit of theory applicable to your cnt function above?

tnx
Baba

Juding from your output, you didn't call the function, you just named
it. To call it you needed to use parentheses, type something like

cnt(5)

The function is a do-nothing function. It makes no calculations, returns
no result. Just illustrating recursion in the simplest way.

Tail call optimization would work fine on that function. CPython doesn't
do such optimization, however. If it did, it would convert the call at
the end to a decrement and a jump. The net effect would be something like:

def cnt(n) :
while True:
if n > 0:
n = n-1
continue
break

Clearly that could be optimized as well. Maybe a great optimizer could
turn it into:

def cnt(n):
pass

DaveA

 

[Ian]

That depends on the language and/or hardware. COBOL wouldn't understand
recursion if hit on the head with a recursion brick and early computer
hardware (those without a stack) made it VERY hard work. If you don't
follow this, look at the CODASYL language specification for COBOL or the
hardware design of ICL 1900 or IBM System/360 mainframes (which are still
the heart of the financial world) and work out how to implement a
recursive function for any of them. Its not easy but it can be done.

That takes me back to Spring 1976 and my first program that wasn't a
print or a validate!
(I had 9 months programming experience!).

It was a costing program for a huge Bill of Materials - ideal for
recursion. It was a re-write
(with extra functionality) from PLAN (the 1900's assembler) to COBOL
ready for a hardware
migration. You are right. Recursion on the 1904 in COBOL was hard work!

The result however was a great success - the new program did more than
the old, ran faster,
was many fewer source lines and was easier to test, so it was really
profitable to write - and
the customer was delighted.

Regards

Ian

 

[Michael Torrie]

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.

 

[John Nagle]

"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

 

[John Bokma]

Not very well.

Based on your reply that follows, I agree.

def cnt(n) :
if n > 0 :
cnt(n-1)


This will work for up to cnt(998), but at cnt(999), CPython
reports "RuntimeError: maximum recursion depth exceeded."

Yes, you can increase the recursion depth, but that case
shouldn't be compiled to recursion at all.

I agree: so this means that Python should eliminate / optimize tail
recursion.

To me, the current value seems a bit low, but I know nothing about
Python internals.

 

[Steven D'Aprano]

this means that Python should eliminate / optimize tail
recursion.

There have been various suggestions to add tail recursion optimization to
the language. Two problems:


* It throws away information from tracebacks if the recursive function
fails; and

* nobody willing to do the work is willing to champion it sufficiently to
get it approved in the face of opposition due to the above.


If you're like me, you're probably thinking that the traceback from an
exception in a recursive function isn't terribly useful. Who needs to see
something like this?
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 3, in recurse
File "<stdin>", line 2, in recurse
ValueError


*yawn*

Would it really matter if Python truncated the stack trace to just the
last line? I don't think so.

But this is not the only sort of tail-call recursion, and a traceback
like the following is useful:

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 4, in recurse
File "<stdin>", line 2, in g
ValueError


If all you saw was the last line (the call to g), debugging the exception
would be significantly harder.

That's a real traceback, by the way, not faked, although it is a
contrived example which I shan't bother to share. The point is not my
specific recursive example, but that not all recursion is direct and
therefore losing the stack traces can be a real cost.

There's more information here:

http://www.tratt.net/laurie/tech_articles/articles/tail_call_optimization


I think it says something that (so far as I know) none of the other
Python implementations have added this optimization. Java doesn't have it
either.

Me personally, I'd like to see either a (preferably) run-time setting or
compile-time switch that enables/disables this optimization. Even an
explicit decorator would be fine. And lo and behold:

http://hircus.wordpress.com/2008/06/21/python-tail-call-optimization-done-right/
http://groups.google.com/group/comp.lang.python/msg/9b047d1392f2b8ec


Add it to your bag of tricks and have fun.

 

[Hrvoje Niksic]

* It throws away information from tracebacks if the recursive function
fails; and [...]
If you're like me, you're probably thinking that the traceback from an
exception in a recursive function isn't terribly useful.

Agreed. On the other hand, a full-fledged tail recursion optimization
might throw away more than that. For tail recursion elimination to work
for those used to it, it needs to also handle the case of mutually
recursive tail calls. The obvious way is by eliminating *all* tail
calls, not just recursive ones.

Tail call optimization, as opposed to tail recursion optimization, means
that code such as:

def f(n):
return g(n + 5)

is executed by a conceptual "jump" from the body of f to the body of g,
regardless of whether recursion is involved at any point in the call
chain. Now, if invocation of g() fails, the stack trace will show no
sign of f() having been invoked. On the other hand, if f() invocation
remains stored on the stack, mutually recursive functions will overflow
it. Python being dynamic, I would expect it to be impossible to
determine at compile-time whether a tail call will ultimately lead to a
recursive invocation.

 

[John Bokma]

this means that Python should eliminate / optimize tail
recursion.

There have been various suggestions to add tail recursion optimization to
the language. Two problems:
[snip]

But this is not the only sort of tail-call recursion, and a traceback
like the following is useful:

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 5, in recurse
File "<stdin>", line 3, in f
File "<stdin>", line 4, in recurse
File "<stdin>", line 2, in g
ValueError


If all you saw was the last line (the call to g), debugging the exception
would be significantly harder.

Yup, agreed, good example.

Me personally, I'd like to see either a (preferably) run-time setting or
compile-time switch that enables/disables this optimization. Even an
explicit decorator would be fine. And lo and behold:

http://hircus.wordpress.com/2008/06/21/python-tail-call-optimization-done-right/
http://groups.google.com/group/comp.lang.python/msg/9b047d1392f2b8ec


Add it to your bag of tricks and have fun.

Thanks for the links. And yes, I will add this to my bag of tricks
(aka local wiki with notes ;-) ).

 

[John Nagle]

There have been various suggestions to add tail recursion optimization to
the language. Two problems:


* It throws away information from tracebacks if the recursive function
fails; and

* nobody willing to do the work is willing to champion it sufficiently to
get it approved in the face of opposition due to the above.

I would rank tail recursion way down on the list of things which
make CPython slow.

(Unladen Swallow seems to have stalled. Last quarterly release,
October 2009. Last wiki update, May 2010. Last issue advanced
to "started" state, Feb. 2010. There are still code checkins,
so somebody is still working, but little visible progress.
They did get a JIT working, but discovered that the performance
improvement was very slight. They wanted at least 5x; they got
1x to 2x at best.)

John Nagle

 

[Bruno Desthuilliers]

Steven D'Aprano a écrit :

FSM? Flying Spaghetti Monster?

Lol. Now this would at least be a pretty good description of the kind of
code base these guys were used to !-)

Was there anything they *did* understand,

Hmmm.... good question - but I didn't last long enough to find out.

or did they just bang on the
keyboard at random until the code compiled? *wink*

Kind of, yes.

 

[Bruno Desthuilliers]

BartC a écrit :

You underestimate how much programming (of applications) can be done
without needing any of this stuff.

From personal experience : almost nothing worth being maintained. I'm
talking about complex domain-specific applications here - not shell
scripts or todo-lists.

I guess they wanted code that could be maintained by anybody.

The code base was an unmaintainable, undecipĥerable mess loaded with
global state (litteraly *hundreds* of global variables), duplication,
dead code, and enough WTF to supply thedailywtf.com for years - to make
a long story short, the perfect BigBallOfMudd. FWIW, the company didn't
last long neither - they just kept on introducing ten new bugs each time
they "fixed" one.