The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
TechInterview.org
CityDesk
FogBugz
Fog Creek Copilot


The Old Forum


Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

Recursion, Why I don't just get it, help?

Hello,

I do understand what do you mean by *recursion* and I do understand all the textbook examples, but when it comes to applying recursion to any true real world application I just fail. It's not that I don't spend enough time on understanding the problem and attacking it. I do spend a lot of time with pencil and paper and then hit my head hard against IDE but I just don't get recursion. I've programmed in C for quite some time and I do get pointers, but I always have a big mental block when its about recursion. What should I do? I aspire to be a hardcore programmer who understands recursion. What should I do? Should I try hard solving textbook exercises, what else I can do to improve on my deficiency?
I really want to have a strong grip on recursion and every other topic that would allow my resume to get pass Joel's resume filter.
Any help in this regard will highly be appreciated.
Thanks in advance.
Thanks,
Recursive
Recursion. see recursion Send private email
Monday, December 11, 2006
 
 
Recursion doesn't come up much in day to day programming for most people.

Find a good textbook and find a term project. Good example - a recursive descent parser for a small language. Something where recursion is at the very heart of the operation.
.
Monday, December 11, 2006
 
 
Many books and resources don't explain recursion well. Without seeing the resources you've seen, I can't be sure about the problem. Here's a shot in the dark:

Has recursion been explained to you in the more abstract sense of solving the first bit of a problem, then solving the rest? For instance (to use a silly, contrived, but easy to program example), you can find the length of a string recursively by breaking it into two parts: the first character and the rest of the string. The length of the string is then 1 (the first char) + the length of the rest of the string. In other words:

size_t my_strlen(const char *s)
{
  if (s[0] == '\0')
      return 0;
  else {
      const char *rest = s + 1;
      return 1 + my_strlen(rest);
  }
}


Does that make any sense to you?
clcr
Monday, December 11, 2006
 
 
I don't know what kinds of problems everyone else here deals with, but in my business database management development career I've only created recursive algorithms twice - in 20 years.

Don't worry about it. If/when the need arises, you'll recognize it & will know what to do.
Karl Perry Send private email
Monday, December 11, 2006
 
 
According to my professor:

Only use recursion when the problem screams out for it.
AnonY
Monday, December 11, 2006
 
 
Thank you for replies fellas
clcr--Yup I do understand it, but it goes off the top of my head when it comes to *real* world problems and problems that are bigger in nature than the ones explained in textbooks.

karl--You are dead on. You said the same thing that my senior programmer told me this morning. But I just want to try and solve hard problems in Recursion and get over it. I don't want my self to stare at deep blue sky when I'll come across recursion after twenty years for the second time:)

I mean something that makes sense more than textbooks, moreover, I want to handle some hard recursive problems so that I should never say NO in an interview question that relates to Recursion. Now what should I do to imrpove my *recursion* skills?
I hope I've made my self clear. Thanks.
Recursion. see recursion Send private email
Monday, December 11, 2006
 
 
I'm with Karl. I've been at it as long as he has and I've used it a couple of times. In both cases I was traversing a tree type structure (menu system and file system) so it made sense to just call the main processing function recursively.
dood mcdoogle
Monday, December 11, 2006
 
 
I think for something to be a candidate for recursion it needs to have two properties:
1. That the problem may, with almost any expected input, be divided into two sub-parts (see point 2 for the exception), one of which is solved by applying the same algorithm to the sub-part and then combining that result with the other sub-part.
2. That there is a clear stopping condition. i.e. a point at which applying the algorithm to a sub-part will not devolve into further sub-parts.
JAG Jr. Send private email
Monday, December 11, 2006
 
 
It wasn't until I learned Lisp that I fully grokked programming with recursion.  Go out and get yourself a copy of "The Little Lisper" or Schemer and do every exercise.  I promise that if you do that you will find thinking with recursion as easy and natural as looping (or easier, when you are dealing with a recursive data structure.)

Learning a language like ML will also do that for you, but I don't know of an ML book comparable to Little Lisper/Little Schemer.

The vast majority of my professional programming life I've used C/C++/Java, not Lisp/ML; but over the years I've probably used recursion 3-6 times a year -- not a daily thing but still a critical skill.
Will Dowling Send private email
Monday, December 11, 2006
 
 
You might be trying to use recursion on problems that don't need it.  If recursion is so infrequently used, why is that?  Because people don't get it (very possible) or that it isn't necessary (also likely).  The string example is a good example, but I doubt he'd use that in the real world when a simple while loop would suffice.
Ryan Phelps Send private email
Monday, December 11, 2006
 
 
"Now what should I do to imrpove my *recursion* skills?
I hope I've made my self clear. Thanks."

Ok, so you understand the basic mechanics. I'd suggest working with tree structures a bit. They lend themselves naturally to recursive approaches (iterative traversal is possible but less obvious), and most if not all of the real-world uses for recursion that you're likely to encounter will involve trees.

Start by implementing a binary search tree. Implement traversal (count nodes, find node by value), insertion, and deletion recursively. Then reimplement using an iterative approach. If you run into trouble, http://tinyurl.com/y54td4 is a good if not cheap resource. With that done, you should understand things quite well.

You might also consider picking up a text on discrete maths. Recursion is directly related to mathematical induction.
clcr
Monday, December 11, 2006
 
 
"The string example is a good example, but I doubt he'd use that in the real world when a simple while loop would suffice."

Correct. Actually I'd just call strlen, but if I had to implement my own it would be iterative. Tree traversal, OTOH, I implement recursively unless there's reason to believe that the tree will be too big to traverse in the available stack space.
clcr
Monday, December 11, 2006
 
 
Thanks everyone.
Will Dowling, one of my friends gave my the same advice. Lately, I've been trying to give "A little Schemer" a try. What do you suggest? I come from a Assembly(i80x86, Motorola 68000)C,C# background?
Do you think learning scheme from "A little Schemer" would help? How should I start learning scheme? I mean is there any IDE for scheme for Windows? I am not sure if I am making sense here :)

Please reply, will be highly appreciated.

Thanks.
Recursion. see recursion Send private email
Monday, December 11, 2006
 
 
Since recursion is rarely used, and in many cases where it is used, it is suboptimal, wasteful or wrong, I'm not sure what the point here is?
Cade Roux Send private email
Monday, December 11, 2006
 
 
The only instance in which I have used recursion productively in real life has been in the instance of parsing strings that contain algebraic expressions in "infix" notation (normal algebraic formulas with operators between operands and parenthesis.) Recursion isn't regarded as the best solution for this problem, but it falls out as an "obvious" way to deal with nested expressions.

If you want to get a grasp of recursion, I would say - write yourself a simple algebraic expression parser that allows parentheses to group subexpressions. You will see fairly quickly.
Bored Bystander Send private email
Monday, December 11, 2006
 
 
> Learning a language like ML will also do that for
> you, but I don't know of an ML book comparable to
> Little Lisper/Little Schemer.


Well, except for _The Little MLer_, by the same authors.


Work through the exercises in _The Little Schemer_. They're all quite tiny; you don't need an IDE. Any ol' command-line Scheme will do.

If you're not comfortable at the command line, you could do far worse than to pick up DrScheme, available at drscheme.org.
Mark Jeffcoat Send private email
Monday, December 11, 2006
 
 
"Recursion doesn't come up much in day to day programming for most people."

I really disagree with this. It may only be NECESSARY every now and then, but it's often useful.

Looking back, my first application of recursive technique was implementing a directory-browser (reading contents of directories and representing in a web app) which is a common scenario used in textbooks.

There are millions of examples of recursion all over in the world. I don't know if any of them would actually help a person that doesn't understand, though.

It's all about breaking down a complex activity into a smaller activity that gets repeated.

Another pivotal piece for me was understanding the concept off the Call Stack. If you don't grasp the call stack, go read about it.
Shane Harter Send private email
Monday, December 11, 2006
 
 
You could also check out the SICP book online from MIT.

I'm not a hardcore programmer, but after Ch.1 of SICP I was able to write a recursive version of C's POW(x, y) in Python. I also wrote a recursive version of of Perl's CHOMP in C, to strip multiple \n from a text stream.

Nothing huge, but I was happy with the results.
*myName
Monday, December 11, 2006
 
 
I find that smart alecks like to ask about recursion on "technical tests".

In 20+ of professional coding, I've very rarely had it come up. It's really cool when you do get to use it, you feel really smart.
Steve Hirsch Send private email
Monday, December 11, 2006
 
 
People like Recursion because it can seem like magic.  Just write this tiny little routine, that calls itself, with the proper exit criteria (recursion MUST end at some point) -- and you're done.

This can have enormous power, in terms of finding certain answers with very little code.  And the idea of a 'routine calling ITSELF' is a little radical.

There's a problem with recursion.  Which is, every time the routine calls itself, it puts a new copy of its data on the stack, along with a return address.  When the recursion FINALLY ends (whether a factorial process reaching 1, or a linked-list reaching the end of the list, or a tree-traversal algorithm reaching a leaf node) then the recursion 'unwraps' -- every call 'returns' to the previous call, which immediately 'returns' to the previous invocation.

The problem is, most real computers have way more memory than they have stack space.  If your recursion is "too deep" (and there's no way I know of to predict how deep it's going to go) you "overflow the stack" and your program exits.  If you never reach the 'exit condition', you're guaranteed to 'overflow the stack'.

So iterative algorithms are actually more robust (less likely to crash, errors more easily handled) and can in fact be FASTER than an equivalent recursive approach.  But they'll take a few more lines of code to implement.  And they won't have that magical, sexy 'ooh, it CALLS itself!' feature to them.  You should get over this aspect, robust is WAY more useful than sexy.

For some limited applications -- tree traversal of a linked list being one of them -- they can make sense.  Otherwise, they should be avoided.
AllanL5
Monday, December 11, 2006
 
 
As an addition, in my experience a problem cries out for recursion when
- it can be splitted into identical sub-problems
** AND **
- it is absolutely necessary to return to the current state after completing at least one of the sub-problems, i.e. the current state must be memorized, which is automatically done on the stack.

Most other problems can as well be expressed in an iterative solution, which is usually faster and more efficient.

E.g. in a binary search tree:

Insert an element with a possible rebalance of the tree: Recursive (the rebalance might be necessary up to the root from the bottom up, thus the whole path down must be memorized).

Count the elements in a tree: Half-recursive (Count+1, recurse left, return here, iterate right -- no need to return).

Search an element in the tree: Iterative (return the current if equal, go left if less, go right if greater, return 'not found' if no left or right, no need to go elsewhere).
Secure
Monday, December 11, 2006
 
 
When I interview candidates and feel the need to ask a question about recursion, I generally want to know their thought process. I think Joel likes this question too because it's rarely taught in "Learn Java in 24 hours" style books.

In other words, I don't ask for syntax correct, bug free code or recognizing that recursion is the "one true way" of solving a problem. What I do want to know is that the candidate realizes there are many different ways of looping (for, while, do, until, recursive, etc) and some solutions are better than others given the problem. I also give credit if the candidate is able to explain why recursion is not a good idea.

I don't know how you'd express this on a resume, but given the way the original poster is talking about this subject, I think he will do just fine during one of Joel's interviews.
TheDavid
Monday, December 11, 2006
 
 
think "circle"
lemon obrien Send private email
Monday, December 11, 2006
 
 
If your language is naturally iterative (for, while, imperative) you won't use recursion a lot, except for trees.  Some languages use recursion because they're based on immutable values and lack iterative constructs.  Problems can be solved in either form (iteration can be defined as a recursive process) but can be ugly & fast in one form, but slow in the other.

If you're doing a lot of fudging in an iterative algorithm, storing immediate values, pushing, popping them or your iteration is really ugly that's a good sign you *might* want to try a recursive process instead. 

That said, the only way you get really good at recursion is to program in a language that requires it or for problems that require it.  OCaml is a bit of oddball in that it supports both imperative and functional styles and has some good tutorials.  Play with it.  Write some code in it. 

Otherwise don't sweat it.
Anon
Monday, December 11, 2006
 
 
"Some languages use recursion because they're based on immutable values and lack iterative constructs.  Problems can be solved in either form (iteration can be defined as a recursive process) but can be ugly & fast in one form, but slow in the other."

No. Probably the languages you're thinking of here are Haskell or Scheme. First of all you can add for/while-like constructs from C/Pascal as syntactic sugar (macros/lazy evaluation let you do this). This is helpful for when you want to isomorphically transcribe code you find in a book or a paper or are translating code from an imperative language and just want to get something that's correct first before worrying about style.

Secondly, tail recursion is equivalent to iteration (that's probably the single fundamental idea in Scheme) and any compiler that isn't retarded will ensure efficient recursion if you write your code in tail recursive form. Thus you do not in fact pay a penalty for it. That is why Scheme can be implemented efficiently. That is the curse of the Blub programmers: they think using programming constructs not conceived in the 1950s or '60s necessarily involve severe efficiency penalties, even though Java is almost as fast as C++ now.

Recursion pops up more than you might think, popular languages just make it tedious and boring to do. Pattern matching and good compilers -- the tools Real Programmers have no need for -- make life nicer.
bleh
Monday, December 11, 2006
 
 
+1 to using tree structures to get your head around them.  I have used them twice in the last 10 years.  One time it envolved a tree and another time it was a directory structure, which really is a tree anyway. 

As for how to understand them.  Good luck with that.  It was one of those Ah Ha! moments in my second programming class.  It is similar to understanding pointers, some people take a while to get to that point.
Brooke Jackson
Monday, December 11, 2006
 
 
Languages that allow recursion but rely chiefly on iteration typically implement recursion on the program stack, leading to the runtime problems already noted. The alternative is worse, so naive recursion will always be the case there. In contrast languages such as Lisp that rely on recursion avoid stack overflow by translating tail recursion into iteration under the hood. Just because the language seems unconcerned with efficiency doesn't mean its interpreter is. Eschewing recursion in favor of iteration for fear of stack overflow smacks of premature optimization. In practice, on a general-purpose computer, I have to try very hard to overflow the stack when using recursion reasonably.

Recursion is not powerful because it offers needlessly clever ways to do ordinary things, or even because it elegantly solves a certain class of problems. It is powerful because learning it teaches you to think about problems in terms of only two cases: basic and general. This mindset helps you separate variant from invariant conditions in your solution, avoiding lots of messy stabs at what you think might be special cases. Then if you decide to implement your solution iteratively for whatever reason, your iterative code will be cleaner.

Recursion only occasionally makes better programs, but it very often makes better programmers.
Jay Windley Send private email
Monday, December 11, 2006
 
 
Actually I meant either form can be ugly and slow, not recursion is slow and iteration is fast.  I've seen some really ugly iterative versions of algorithms which were slower than the recursive version and some slow recursive versions which had extremely fast iterative counterparts.  Some algorithms are simpler and or faster in one form or the other.  It just depends on the problem.

My point was learning recursion can help avoid complex code but not always.
Anon
Monday, December 11, 2006
 
 
"+1 to using tree structures to get your head around them.  I have used them twice in the last 10 years.  One time it envolved a tree and another time it was a directory structure, which really is a tree anyway. "

Agreed.  It is a shame that books often use factorial calculation as an example of recursion.  yes, mathematically, it is often expressed as a recurrent relationship.  No, we (programmers) should never calculate it as a recursive function.

Like others, I found myself using recusrion in the "real world" quite rarely - twice in 10 years in my case (if my memory is correct).

Despite my lack of "real world" examples, I'm surprised at how often recursion comes up in student programs.  For example, given a 2-dimensional array of colors (or shapes or whatver), finding all instances of 3 or more adjacent squares of the same color (think Bejeweled or Gem Drop) is anatural recursion problem.  Given a Boggle board, find all valid words is also a natural recursion problem.  It does solve certain problems rather neatly.
coderprof Send private email
Monday, December 11, 2006
 
 
I am comfortable with recursion, but it just does not come up in my work.  It is a nice hammer, but.

Many of the textbook examples that I have seen are stupid.  The classic is computing factorial with recursion.  Iteration is obviously less trouble.  That is not a good way to introduce a powerful tool.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Monday, December 11, 2006
 
 
I once had to write a pricer for financial instruments.
The instrument could be a stock, or a basket of other
financial instruments. The price of a basket was determined
by the price of its constituents. Solved recursively.

I once had to write an editor for a folder hierarchy,
which included functions such as copy this folder
(including its children, which can be folders).
Solved recursively.

Also an AI problem (a board game player) that had to
choose from a tree of possible moves and countermoves
what the best nextmove would be. Solved recursively.

All written in C++ and Java.
You could practise on the directory editor example?
Monday, December 11, 2006
 
 
"Recursion only occasionally makes better programs, but it very often makes better programmers."

After all, this thread in special and the problem of recursion in general is somehow fascinating, since recursion as-is is nothing special -- it is a function call like any other function call to solve a specific problem, just like any other function solving another specific problem. The art seems to be that one must realize that the problem to be solved by the function call is identical to the problem currently solved in the current function.

Thus maybe the barrier to understanding simply lies in the fact that the function calls itself, confusing things, instead of a well-separated external function? Maybe together with a fundamental misunderstanding of variable storage -- the local variables are not overwritten, any call has its own set? Maybe it boils down to the understanding of memory and memory addressing, just like pointers?

Question to the OP: Do you understand memory and memory addressing? I mean, really? Do you understand the concept of the CPU stack, down on the binary level of individual memory bytes?
Secure
Monday, December 11, 2006
 
 
Huh. I use recursion all the time.

Admittedly, I've written several different kinds of parsers and expression evaluators. One cool recursive project was reading a list of regular expressions, combining them all into a single deterministic finite automaton, and then re-writing them all as a single regex. Pretty cool.

But many of my projects involving recursion were much simpler. Like crawling a directory tree, looking for certain types of files. Or crawling through a source code repository looking for cyclic dependencies.

There are a zillion different problems that just scream for a recursive solution. Actually, the cyclic dependency checker was a great example. Given some large repository of source code files, I'd like a complete list of the cyclic dependencies. Ready...Go!!!
BenjiSmith Send private email
Monday, December 11, 2006
 
 
#include <stdio.h>

void Rot13( char * s )
{
    char c = (*s) ;
    if ( c != '\0' )
    {
        if (
            ( ( c >= 'A' ) && ( c <= 'M' ) ) ||
            ( ( c >= 'a' ) && ( c <= 'm' ) )
            )
        {
            c += 13 ;
        }
        else if (
            ( ( c >= 'N' ) && ( c <= 'Z' ) ) ||
            ( ( c >= 'n' ) && ( c <= 'z' ) )
            )
        {
            c -= 13 ;
        }
        
        Rot13( s+1 ) ;
    }

    return s ;
}


int main( int argc, char * argv[] )
{
printf( Rot13(
"Nal erphefvir (abg whfg gnvy-erphefvir, be nhtzragvir-erphefvir) shapgvba pna or "
"rkcerffrq nf n vgrengvir shapgvba. Nal vgrenpgvir shapgvba pna or rkcerffrq nf n "
"erphefvir shapgvba. Yrnivat nfvqr uvtu-yriry ynathntrf gung unir yvzvgngvbaf jvgu "
"erphefvba be vgrengvba (jurer lbhe pubvpr znl or sbeprq) - gur nqinagntr bs bar "
"bire gur bgure, vfa'g gung bar pna qb gung gur bgure pna'g (orpnhfr gurl obgu pna "
"qb gur fnzr guvatf), ohg bar znl bssre n orggre jnl bs rkcerffvat pregnva nytbevguzf.  "
"Sbe rknzcyr, fbzr nytbevguzf, ner zhpu zber fvzcyl rkcerffrq hfvat erphefvba (r.t. "
"Dhvpxfbeg, Gerr Genafirefny) - rira gubhtu gurl pna or rkcerffrq hfvat vgrengvba naq "
"n fgnpx (znal lrnef ntb, V unq gb vzcyrzrag n Dhvpxfbeg va n qOnfr inevnag - juvpu "
"qvqa'g nyybj erphefvba - naq juvpu vaibyirq zrzbel onfrq qngn - naq ng gung gvzr, vg "
"ernyyl uheg abg gb unir erphefvba).  Gur ernyyl ovt ceboyrz jvgu erphefvba, vf gur "
"pbfg bs qrrc erphefvba va grezf bs fgnpx zrzbel, V guvax NyynaY5 fbzrjung haqrefgngrf "
"gur ceboyrz.  Bu, naq V nterr snpgbevny (naq nabgure snibevgr vf sybbq svyy) ner "
"greevoyr qrzbafgengvbaf bs erphefvba.  Naq fb vf guvf rknzcyr."
"\n"
"Sbe gur erpbeq, V unir hfrq erphefvba znal gvzrf (n ybg zber guna bapr rirel 10 lrnef!), "
"ohg gur ahzore bs erny hfrf sbe vg (ynathntrf juvpu sbepr vg rkprcgrq), ner nyjnlf yrff "
"guna gur erphefvba-snangvpf (naq gurer ner fbzr bhg gurer), guvax."
"\n"
 ) ) ;
}
Sunil Tanna
Monday, December 11, 2006
 
 
Sorry I lost  a line

#include <stdio.h>

void Rot13( char * s )
{
    char c = (*s) ;
    if ( c != '\0' )
    {
        if (
            ( ( c >= 'A' ) && ( c <= 'M' ) ) ||
            ( ( c >= 'a' ) && ( c <= 'm' ) )
            )
        {
            c += 13 ;
        }
        else if (
            ( ( c >= 'N' ) && ( c <= 'Z' ) ) ||
            ( ( c >= 'n' ) && ( c <= 'z' ) )
            )
        {
            c -= 13 ;
        }

        (*s) = c;
        
        Rot13( s+1 ) ;
    }

    return s ;
}


int main( int argc, char * argv[] )
{
printf( Rot13(
"Nal erphefvir (abg whfg gnvy-erphefvir, be nhtzragvir-erphefvir) shapgvba pna or "
"rkcerffrq nf n vgrengvir shapgvba. Nal vgrenpgvir shapgvba pna or rkcerffrq nf n "
"erphefvir shapgvba. Yrnivat nfvqr uvtu-yriry ynathntrf gung unir yvzvgngvbaf jvgu "
"erphefvba be vgrengvba (jurer lbhe pubvpr znl or sbeprq) - gur nqinagntr bs bar "
"bire gur bgure, vfa'g gung bar pna qb gung gur bgure pna'g (orpnhfr gurl obgu pna "
"qb gur fnzr guvatf), ohg bar znl bssre n orggre jnl bs rkcerffvat pregnva nytbevguzf.  "
"Sbe rknzcyr, fbzr nytbevguzf, ner zhpu zber fvzcyl rkcerffrq hfvat erphefvba (r.t. "
"Dhvpxfbeg, Gerr Genafirefny) - rira gubhtu gurl pna or rkcerffrq hfvat vgrengvba naq "
"n fgnpx (znal lrnef ntb, V unq gb vzcyrzrag n Dhvpxfbeg va n qOnfr inevnag - juvpu "
"qvqa'g nyybj erphefvba - naq juvpu vaibyirq zrzbel onfrq qngn - naq ng gung gvzr, vg "
"ernyyl uheg abg gb unir erphefvba).  Gur ernyyl ovt ceboyrz jvgu erphefvba, vf gur "
"pbfg bs qrrc erphefvba va grezf bs fgnpx zrzbel, V guvax NyynaY5 fbzrjung haqrefgngrf "
"gur ceboyrz.  Bu, naq V nterr snpgbevny (naq nabgure snibevgr vf sybbq svyy) ner "
"greevoyr qrzbafgengvbaf bs erphefvba.  Naq fb vf guvf rknzcyr."
"\n"
"Sbe gur erpbeq, V unir hfrq erphefvba znal gvzrf (n ybg zber guna bapr rirel 10 lrnef!), "
"ohg gur ahzore bs erny hfrf sbe vg (ynathntrf juvpu sbepr vg rkprcgrq), ner nyjnlf yrff "
"guna gur erphefvba-snangvpf (naq gurer ner fbzr bhg gurer), guvax."
"\n"
 ) ) ;
}
Sunil Tanna
Monday, December 11, 2006
 
 
char * Rot13( char * s )
Meghraj Reddy
Monday, December 11, 2006
 
 
gcc will need -fwritable-strings on that.
Meghraj Reddy
Monday, December 11, 2006
 
 
bs, recursion does come up....what is a treeview, a directory structure ect...

you have to walk each node recursively to build a treeview or directory structure, recursively calling a function until there are no more child nodes for a given root.

Monday, December 11, 2006
 
 
Meghraj, yep.

That's what comes from going from Notepad -> Joel without testing.  I did actually spot both the mistakes (the one I spotted, and the one you did) before posting, but somehow I pasted the wrong copy or something, and pasted my first notepad revision.
Sunil Tanna
Monday, December 11, 2006
 
 
" The price of a basket was determined
by the price of its constituents. Solved recursively."

for item in basket do
 basketPrice += price(item)
naturally iterative solver
Monday, December 11, 2006
 
 
naturally iterative solver, what, pray, is the price of each of those items? :)

Suppose that each of those items contains a currently-unknown number of consituent items. (Suppose it's a box of bags of treats, each bag being priced according to the sum of the values of each treat, each of which could contain multiple actual sweats.
Arafangion
Monday, December 11, 2006
 
 
price(item)
 for item in basket do
    basketPrice += price(item)

 return basketPrice
I've learned recursion!
Monday, December 11, 2006
 
 
+1 to AllanL5 and others who suggested to resort to recursion only when absolutely necessary.  It is overrated and often creates more problems than it solves.

One way to wrap your mind around recursion is to replace it with a loop and explicit stack.

For some unknown to me reason interview question about recursion are very frequent.  So it's worth learning.
Jeff Zanooda Send private email
Monday, December 11, 2006
 
 
You'll need to use recursion if your working with greedy or dynamic algorithms
Tony Mony Send private email
Tuesday, December 12, 2006
 
 
To iterate is human,
to recurse is divine
Captain Clueless Send private email
Tuesday, December 12, 2006
 
 
I write recursive code often, and it seems too always be a case of I have a object tree, and I need to write out a html navigation for the tree.

(Yes this could be done as a simple loop, but that would involve a inserting into a string buffer. With recursive code I can write directly to the response stream.)
Gary van der Merwe Send private email
Tuesday, December 12, 2006
 
 
Funny how this topic got quite wildly varying responses.

It surely can't be argued that certain types of algorithms are very naturally expressed using recursive notation.  I'm thinking of stuff like tree traversal, certain types of parsing, quicksort, etc.

It would depend on what sort of programming you do as to whether you encounter this sort of stuff on a regular basis.  I've certainly run into lots of recursion over the years as both a professional and recreational programmer.

It also probably helps to have been exposed to some functional type programming languages where recursion is more common.  Well worth the experience if you haven't tried it.
petermck
Tuesday, December 12, 2006
 
 
"for item in basket do
 basketPrice += price(item)"

Obviously price(...) needs to be recursive when baskets can contain baskets in which case why bother with the for loop in the first place.  Representing the baskets as lists of numbers gives the following obvious recursive implementation:

(define (price b)
  (cond ((pair? b) (fold (lambda (e acc) (+ acc (price e))) 0 b))
        ((number? b) b)
        (else (raise (string-append "Element " (->string b) " has invalid type")))))

;; price test case

(price '(1 (2 3) (4 5 6 (7 8))))

In production code you may want to have slightly more complex items with a representation such as:

(define-struct basket (items))
(define-struct item (type value))

Also, implementation of ->string left as an exercise for the reader.
James
Tuesday, December 12, 2006
 
 
What are all these "downsides" to recursion that people keep talking about? Stack overflows? Is that it?

When working with tree structures you're going to have multiple roll-ups during the course of the operation. This doesn't eliminate stack overflows, but in my experience they're not very common.

Furthermore, the idea that it's slower than iteration I think is difficult to say. So much depends on so many things. A blanket statement like that just doesn't work here.

But even if it is slower, what is the case for premature optimization here? Aren't developer-cycles more important than processor-cycles generally speaking? I can write a 5 line recursive routine for tree traversal. It would probably take 3-4x that to do it with iteration.

Given the option, I would much rather maintain a 5-line recursive method than a 20 line iterative method.

Just me $.03
Shane Harter Send private email
Tuesday, December 12, 2006
 
 
Shane,

just for nitpicking ;)

node *search (node *n, elem key)
{
    int cmp;
    if (n)
    {
        cmp = compare(n->content, key);
        if (cmp < 0)
            n = search(n->left, key);
        else if (cmp > 0)
            n = search(n->right, key);
    }
    return n;
}


node *search (node *n, elem key)
{
    int cmp = 1;
    while (n && cmp)
    {
        cmp = compare(n->content, key);
        if (cmp < 0)
            n = n->left;
        else if (cmp > 0)
            n = n->right;
    }
    return n;
}
Secure
Tuesday, December 12, 2006
 
 
Yes the downside is the stack frames created for each level of recursion, and these stack frames  contain both the caller return address, and more importantly the local variables - which people are often careless about creating because "hey they'll be freed up at the end of the function anyway" - forgetting in the case of a recursive function there may be LOTS of copies of that 1 function's stack frames.

The wise use of recursion, are when it flows naturally from the algorithm, and where it would require a stack to implement iteratively: Things like Quicksort and Tree Traversal.  I suspect it is probably not a coincidence, but these types of algorithm usually have a depth of recursion based on log(N) where N is the number of elements.

The evil use of recursion, because of the considerations in first paragraph of this post, is when the depth of recursion is huge, or is not easily guessible.  Huge example: Calculate Factorial of 1,000,000.  Not easily guessible: Floodfill.  I have seen a Sun workstation brought to its knees by the latter.
Sunil Tanna
Tuesday, December 12, 2006
 
 
Secure,

I'm a C# developer, so I could very well be missing something here, but how would the code you posted search a tree? I suppose it depends on what you have abstracted in the n->left/n->right methods but as I'm reading it, the loop would stop at the end of one branch.

What am I missing?
Shane Harter Send private email
Tuesday, December 12, 2006
 
 
Ahh.. Well, I was comparing your iterative example to what I had in my head, not to your recursive example. Your examples do obviously do the same thing.

FWIW, here's basically what I was thinking (in PHP):

function search($array, $query)
{
    if (is_array($array))
    {
        foreach ($array as $branch)
        {
            if ($branch == $query || search($branch, $query))
            {
                return true;
            }
        }
    }

    return false;
}
Shane Harter Send private email
Tuesday, December 12, 2006
 
 
Also remember that some of us develop on embedded systems with or without RTOS's.  So even if there is a lot of FLASH/ROM for code space, total RAM might only be 1K's to 10K's.  Recursion would quickly overflow a stack space & on for most RTOS's there is NO method to detect & protect stack space overflow at run-time so the system will likely crash hard.
Ian Johns
Tuesday, December 12, 2006
 
 
What a boring life it must be to not be using recursion.
I often build tools.
Tuesday, December 12, 2006
 
 
Good point about the issues of embedded systems.

One thing that occurred to me is that every time I've used recursion it's been in a "finite way." That is, I've never used it for the textbook factoring example. It's always been "iterate this nested array" or "this object hierarchy" etc.
Shane Harter Send private email
Tuesday, December 12, 2006
 
 
If you used tail recursion you would not run out of space with any decent compiler.
Anon
Tuesday, December 12, 2006
 
 
"What are all these "downsides" to recursion that people keep talking about? Stack overflows? Is that it? "

Recursion also can make your code harder to read.  Particularly if you are using indirect recursion (function A calls function B which calls function A...).  And particularly if the reader is one of the many programmers who isn't comfortable with recursion.  So I would argue that there is a maintenance penalty in some cases (see below).  Explicitly documenting the recursion is a good idea to mitigate this.  Instead of This function traverses over a tree..., use This function recursively traverses over a tree..

"Given the option, I would much rather maintain a 5-line recursive method than a 20 line iterative method. "

Agreed.  But take the trvial factorial case.  Is a 4 line recursive function solution better than the 4 line for loop solution?  I would argue decisively "no" simply because most people will understand the for loop in less time than the recursive version.  It takes a certain level of simplification before the increased understandability from a simpler routine overcomes the reduced understandability inherent in recursion.  Tree traversals or expression parsing generally reach that level because the non-recursive version becomes fairly complicated (and probably more error-prone as well).
coderprof Send private email
Tuesday, December 12, 2006
 
 
coderprof,

Interesting points. However, the same thing could be said about many other techniques: Pointers, Regular Expressions, even OOD.

The fact that a developer 'might not understand' clearly-written code is difficult to plan for ahead of time.

I believe in self-documenting code and easy maintenance, but in my opinion that means 'don't do anything too clever.' It doesn't mean 'avoid common techniques because the next guy might not understand.'

I suppose it's like newspapers that always try to write at a level that would be comprehensible by the average 13 year old. They picked a level and said "this is our standard." Nobody to my knowledge has ever done that with software development, but if they did, I'd like to think that such a level would include understanding of such things.

If the two methods really are equal in implementation and function, then yes, chose the most obvious one. But if one method has even a slight edge, I would personally rather use that one.
Shane Harter Send private email
Wednesday, December 13, 2006
 
 
This is a fun topic!

Anyways, it lead me to thinking about TeX, one of the best programs ever written (a typesetting program written by Donald Knuth). It makes extensive use of recursion.
Steve Hirsch Send private email
Wednesday, December 13, 2006
 
 
writing a little program to do directory diving and delete temp files helped me get my head around using recursion
Zach M.
Wednesday, December 13, 2006
 
 
What are the rules here?

Recursion is nice when you can divide one larger problem into two (or more) similar pieces. Recursion in this case allows you to use the same function on the smaller pieces until they become REALLY small pieces where the answer becomes trivial.

Recursion is particularly good when you need to keep some information from each iteration stage until the whole calculation is complete. This information lives naturally in the variables for the function, as they are allocated on the stack.

Recursion is never essential - you can always do the same thing with a looping construct. But if you find yourself allocating a block of memory or array to act as a stack, recursion might be the way to go.

Recursion is NOT the way to go if the depth of recursion is not very well defined. It's also more expensive to call a function than it is to go around a loop (all things being equal).

Most of the time it's used for navigating tree structures of one kind or another. It's never used for factorials except in tutorials - a loop like this is much faster.

double result=x;
while (--x)
{
  result*=x;
}
return result;
Duncan Sharpe Send private email
Thursday, December 14, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz