Your favorite recursive function...

[sans-hubris]

My favorite recursive functions are those simple mathematical functions (like Fibinacci and n-factorial). I saw some code for the Towers of Hanoi problem and thought that was pretty cool too.

What's your favorite recursive function?

[Whipping Boy]

I'd like to see that, actually.

[Strike]

See what? The Tower of Hanoi problem solution? I can't remember where I saw it, but I believe I remember seeing it somewhere as well (as a recursive function call).

The factorial one is easy, basically you just check and see if the argument you are passed is 1, and if it is, return the result you've been multiplying. Otherwise multiply the current number times the factorial of the number one less than the current number.

I can't think of a favorite recursive function call right now. The factorial one is the classic example in my experience.

[Blckglass]

If you go to cs.lafayette.edu (http://www.cs.lafayette.edu) and follow the CS 103 link, download the recursion chapter towards the bottom of the page you will be able to find stuff about the recursive version of Towers of Hanoi in there. I had to code the iterative version, that was fun to say the least.

[ 18 February 2001: Message edited by: Blckglass ]

[Dru Lee Parsec]

Recursion is actually about the WORSE solution for a factorial function. Unfortunatly, all the programming books use factorial as an example when teaching recursion. But the overhead of a recursive method is terrible. Besides, doesn't this make a ton more sense:


// let's do factorial 10 or 10!
long factorial = 1;
int f = 10;

for( int i = 1; i <=f; i++) {
factorial = factorial * i;
}
// Done!




You really don't need anything more complex than that to do factorial.

In Java I don't have to walk trees any more, but when I was doing C++ code I used recursion to walk a Binary Search Tree. However, that's another case where removing the recursion can give you an immediate 10% to 20% increase in speed.

Recursion is fine when it provides an elegant solution to a difficult problem. I just don't think factorial is one of those elegant solutions.

[ 19 February 2001: Message edited by: Dru Lee Parsec ]

[Stuka]

Hey, Dru, I actually found a textbook that states the same! It's our Data Structures book (Data Structures and Program Design in C, by Kruse et. al.), and the only problem it mentions as benefiting from recursion is the Towers of Hanoi. It actually TELLS you that a recursive factorial solution is wasteful. I thought that was pretty cool.

[Dru Lee Parsec]

Wow! That's cool. You have a good programming book. I'm always amazed at how many programming language books use n! as the example when teaching recursion. And it's just the worse thing you could do.

I don't remember the code, but I once saw an article where Michael Abrash wrote a non-recursive binary search tree in-order walk in only 13 lines of C code. SWEET!

But then, Michael Abrash is pretty much a coding god!

[TheLinuxDuck]

I whipped together a resursive hash/array display debug thingie in perl that will parse down a hash/array into all references it contains. Maybe not the most elegant, but ...HEY!! I LIKE IT! :D

[Strike]

Yeah, I think most programming texts (at least the ones I've seen) acknowledge that a recursive factorial function is stupid and wasteful. I just think they use it as an example because it makes it easy to grasp the concept of recursion that way. I mean, people can understand that 7! = 7 * 6! = 7 * 6 * 5! = ... and so forth, because it's common sense to anyone with any math background (which CS majors are required to have anyway). Other things are a bit more esoteric and may not make the concept as easy to understand to the recursive-ignorant.

But, like I said, the texts I have read all agree (as did my professor) - recursion is a stupid way of doing factorial.

[sans-hubris]

Strike, you said it best. My prof. advises very much against tail recursion, but uses n-factorial just so we can get the hang of it.

As wasteful as a recursive n-factorial, you have to admit that the first time you see it, it looks kinda cool.

[jemfinch]

With tail recursion, there isn't any more overhead to a recursive factorial function than there is for an iterative one.

Jeremy

[nanode]

I had to make a GUI menubar editor once. The dialog class would take an actual JMenu as an arg and would unroll it and represent it in the form of a JTree. The user would then drag and drop nodes to various places on the tree. When the user was done modifying the tree a new menubar would be built from walking the tree.

Initially I was using a lot more recursion, but found it more "elegant" and useful to overload a method based on an arg type.

building a menu roughly went like this:

get Next Node
if node is leaf branch is done
else
get Next Node

Unfortunately there ended up being a ton of actual code, but I had a lot of complex GUI behavior (DnD TreeNodes among other things).

[pinoy]

Probably not really recursive functions, but recursive solutions are a great way of building up parse trees. Especially as most grammars if you look at the BNF structures are recursive anyway.

I agree with Dru Lee about the n! function, function calls are expensive, plus stack space is not infinite. Which means a recursive solution for factorials are probably slower and can result in stack overflow, than its loop counterpart

[Stuka]

Lloyd - are you a fan of Design Patterns? It suggests several recursive solutions that create truly elegant designs for certain categories of problems (Composite comes to mind, as does Decorator). I really think anyone doing OOP should be forced to read that book!

[pinoy]

Stuka, I'm a big fan of Design Patterns, in fact before I read the book, I never really liked OOP. I agree with you anyone who wants to do OOP should *really* read this book. At one point I even started a study group here at work, and it is much easier to talk to other developers about design issues if you have names for them.

[nanode]

LloydM:

That's great that you can speak intelligently about OOP with your co-workers. I'm one of 3 serious OOP enthusiasts in our team at work. Actually, one guy got fired and the other is a manager - who doesn't really code, but is great to BS with in the lunch room.

Some people think "class object" is a fancy name for a data struct. :)

[Tyr-7BE]

Towers of Hanoi...why? Because one of my assignments in my first-year programming class was to solve this little diddy. GREAT introduction to recursive functions, and I pulled my hair out for quite some time before I solved it. I tell ya, that was the most satisfying feeling in the world when it started printing out "Move disc from tower 1 to tower 3. Move disc from tower 1 to tower 2." and continued on to complete the problem correctly! An immersion that deep in a recursive problem makes it my favorite :)

[knavely]

im in my first year of computer science too and i just finished my introduction to recursion assignment too. Ours was Pascals triangle, not as hard as the Towers but it was a pretty cool little expierence...

" :rolleyes:hmmm thants not it...na it couldnt be under 10 lines...hmm lets just see what happens if i compile...ok correct output, but i must have messed somewhere, try a different test, mmm hey that worked too, another, wow only 8 lines it works cool! OF course i doess why would i doubt me?" :cool:

[YaRness]

i faked recursion by pushing elements back onto a list in a 'foreach (@list)' type dealio in perl (see TLD's post, it was a similar thingie). it was kinda cool.

of course, my favorite is

sub foo
{
return fork(),foo();
}

:D

[Piix4]

This is gpl'd unless it's for homework ok?
In which case I want $5.00 ok?

#include <stdio.h>

double hanoi(int disks,int start,int end,int tmp);
double print_hanoi(int disks,int start,int end,int tmp);
int main(int argc,char**argv)
{
int disks,start,end,tmp,print=1;
double moves;
if(argv[1])
print=0;
printf("Please enter number of disks : ");
scanf("%d",&disks);
printf("Please enter start disk num : ");
scanf("%d",&start);
printf("Please enter end disk num : ");
scanf("%d",&end);
printf("Please enter buffer disk num : ");
scanf("%d",&tmp);

switch(print)
{
case 0:
moves=print_hanoi(disks,start,end,tmp);
break;
case 1:
moves=hanoi(disks,start,end,tmp);
break;
default:
break;
};
printf("Moving %d disks took %g moves\n",disks,moves);
return 0;
};

double print_hanoi(int disks,int start,int end,int tmp)
{
static double ret=0;

ret++;
disks--;

if(disks==0)
{
printf("%d-->%d\n",start,end);
}
else
{
print_hanoi(disks,start,tmp,end);
printf("%d-->%d\n",start,end);
print_hanoi(disks,tmp,end,start);
};
return ret;
};

double hanoi(int disks,int start,int end,int tmp)
{
static double ret=0;

ret++;
disks--;

if(disks==0)
{
}
else
{
hanoi(disks,start,tmp,end);
hanoi(disks,tmp,end,start);
};
return ret;
};

[The Kooman]

Originally posted by ndogg:
<STRONG>My favorite recursive functions are those simple mathematical functions (like Fibinacci and n-factorial). I saw some code for the Towers of Hanoi problem and thought that was pretty cool too.

What's your favorite recursive function?</STRONG>

Ok, I'm posting this after seeing everybody crib about n! not being a good example for recursion because its inefficient. But, IIRC, most compilers (and even interpreters that do intermediate compiling) will optimise tail recursion into a loop. I think recursion, if understood and used correctly and appropriately, is beautiful and elegant. Recursion may not be operationally efficient but it may be very programmer efficient. I don't mind doing a few cycles less but being able to understand my code 3 years from now :D!

As for recursive problems ... How about:
8 queen's problem
Generate all permutations of a set of n elements
Knight's traversal problem
Any lisp problem :D heh, heh!


Just my $0.02!

[TacKat]

But, IIRC, most compilers (and even interpreters that do intermediate compiling) will optimise tail recursion into a loop.

IMHO, this is a Very Bad Thing (TM). It encourages sloppy programming, because hey, the compiler will take care of it, right?

[TaeShadow]

In my C++ class last semester, I wrote a recursive function that solved a maze. That was fun.

[sans-hubris]

Whoa, talk about resurrecting the dead.

Umm, well, right.

This brings up an interesting thought I had. I wonder if it would be considered recusion if there were two functions (a() and b()) that kept calling each other until one of them comes to a base case. Of course, this really wouldn't be limited to just two functions, but something where its circular.

[ 09 September 2001: Message edited by: Muad Dib --formerly ndogg ]

[jemfinch]

Originally posted by TacKat:
IMHO, this is a Very Bad Thing (TM). It encourages sloppy programming, because hey, the compiler will take care of it, right?

Recursion isn't sloppy programming. Recursion is the most general, capable, and simple looping construct.

Not optimizing tail recursion into a loop is sloppy compiler writing. Also remember that tail recursion optimization is a requirement in the definition of several languages, including Scheme, O'Caml, and SML.

People need to realize there have been significant advances made in programming language design and compilation and that opinions based on the fact that the language they're using just hasn't taken advantages of those advances need to be qualified with the appropriate language.


Recursion is actually about the WORSE solution for a factorial function. Unfortunatly, all the programming books use factorial as an example when teaching recursion. But the overhead of a recursive method is terrible.


Maybe in Java, and C, and C++, but not in Scheme, or O'Caml, or Standard ML, or most implementations of Common LISP.


I don't remember the code, but I once saw an article where Michael Abrash wrote a non-recursive binary search tree in-order walk in only 13 lines of C code. SWEET!


Since walking the tree is easily implemented tail recursively, it really would only mean using goto and a label. It's not really hard to write such a thing in C; what he wrote was probably the same code that a compiler that properly optimized tail recursion would do.


Yeah, I think most programming texts (at least the ones I've seen) acknowledge that a recursive factorial function is stupid and wasteful.


Again, only in languages that don't optimize tail recursion. Recursion is not universally stupid or wasteful.

Sorry to post to a long-dead thread, but I really needed to get this out :)

Jeremy

[nanode]

Is it just me or have several historic threads (several months old) been bumped up recently?

[TacKat]

I wasn't really referring to recursion as being sloppy - it's not if you use it in the right situations. I was talking more about when the compiler takes a recursive function and turns it into a loop instead. If the process is handled better through a loop, the programmer should have written it as such, not relied on the compiler to clean up for them.

[jemfinch]

Originally posted by TacKat:
I was talking more about when the compiler takes a recursive function and turns it into a loop instead. If the process is handled better through a loop, the programmer should have written it as such, not relied on the compiler to clean up for them.

You're still thinking language centrically.

Many languages guarantee that tail recursion is optimized into a loop. Many languages, because of this guarantee, don't even bother offering any other looping constructs. It's not sloppy programming to use recursion; it's sloppy compiler writing (or language specification) to not optimize tail recursion into a loop.

Using recursion only becomes "sloppy" when the language you're using doesn't handle it optimally.

Jeremy

[TacKat]

Okay I think I see your point. I guess I'm just one of those strange people that doesn't want anything put into a program that I didn't specifically put there. Must be why I like assembly. :)