Recursion

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

User avatar
Clumpy
Posts: 1883
Joined: Thu Jul 19, 2007 4:48 am UTC
Contact:

Recursion

Postby Clumpy » Fri Dec 21, 2007 12:19 am UTC

On a similar note, is recursion very crucial?

EDIT: I just noticed that this is a separate topic, which I don't remember creating. Did a moderator do this? My "on a similar note" wouldn't make sense as the start of a new thread. . .
Last edited by Clumpy on Sun Dec 23, 2007 7:45 am UTC, edited 1 time in total.

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Beginning in Computer Science

Postby segmentation fault » Fri Dec 21, 2007 12:44 am UTC

Clumpy wrote:On a similar note, is recursion very crucial?


If you're not being sarcastic, its just about the worst thing ever :P
people are like LDL cholesterol for the internet

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Beginning in Computer Science

Postby btilly » Fri Dec 21, 2007 2:22 am UTC

Clumpy wrote:On a similar note, is recursion very crucial?

It depends on what you want to do. If your aim is to flip burgers, then you have no need to learn recursion. If your aim is to program computers, learning recursion would be a good idea.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 3:26 am UTC

btilly wrote:
Clumpy wrote:On a similar note, is recursion very crucial?

It depends on what you want to do. If your aim is to flip burgers, then you have no need to learn recursion. If your aim is to program computers, learning recursion would be a good idea.

That depends, do you plan on flipping lots of burgers? If so, recursion might be beneficial.


And as far as "programming and recursion" going hand in hand... Turing machines aren't turing machines unless they recurse. In fact, most ideas in programming, period, aren't going to work at all without recursion. You need to have recursion, you need to have things that repeat based off of things before.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
Clumpy
Posts: 1883
Joined: Thu Jul 19, 2007 4:48 am UTC
Contact:

Re: Beginning in Computer Science

Postby Clumpy » Fri Dec 21, 2007 3:56 am UTC

segmentation fault wrote:
Clumpy wrote:On a similar note, is recursion very crucial?


If you're not being sarcastic, its just about the worst thing ever :P


Nope. I wasn't being sarcastic, but I wish I was :). I just started beginning Computer Science and am enjoying it except for the mindfreak that is recursion. I'm sure I'll get it eventually.

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 4:20 am UTC

Recursion shouldn't be a mind freak, it's just an every day thing in an out of the ordinary circumstance. The problem is most students of programming to my knowledge thing programs are these very linear things that go from start to finish and may only once in a while loop over itself for a wee bit. That's not really very complex programming at all and it's poorly suited to a lot of problems. Really interesting programs start and end in multiple places and will recurse over themselves a lot.


Here, go to this website. When you get it, you'll know what recursion is:

Recursion at the Jargon File
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
Clumpy
Posts: 1883
Joined: Thu Jul 19, 2007 4:48 am UTC
Contact:

Re: Beginning in Computer Science

Postby Clumpy » Fri Dec 21, 2007 6:34 am UTC

Thanks for the link. That's a pretty fitting definition. :)

spelunker
Posts: 102
Joined: Wed Dec 05, 2007 7:07 am UTC

Re: Beginning in Computer Science

Postby spelunker » Fri Dec 21, 2007 6:59 am UTC

Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Don't get me wrong, every programmer worth his salt should understand recursion and be able to do it; I just don't use it a lot...

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Beginning in Computer Science

Postby segmentation fault » Fri Dec 21, 2007 5:18 pm UTC

recursion is a simple concept. take factorial for instance. 5! is really 5 * 4!, which is really 5*4*3! and so on until you hit 1.

the bad thing about implementing it is your call stack explodes.

limit its use.
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 7:07 pm UTC

If you're implementing recursion the naive way in which you make recursive function calls, you're probably not doing it right. There's too much overhead (and the call stack is a pretty imposing barrier) so what you do is you write your recursive function so that it doesn't need to call itself, it simply loops over itself.

Code: Select all

pseudocode factorial function
factorial(x) {
    returnval = 1;
    while (x > 1)
        returnval *= x--;
    return returnval;
}


What that does is start with a return value of 1, and checks if x is less than or equal to 1 (either a 0 or a 1, we're assuming unsigned ints here.) If so, skip the loop and return the returnval (it's 1 for both cases.) Otherwise, multiply the returnvalue by x, and decrement it. The "x--" is shorthand for saying "subtract 1 from x, but still treat it as x in this statement." That means when you run the code, if you input x = 5, then it still multiplies returnval by 5, but immediately after that statement, x is equal to 4, not 5. This line: "returnval *= x--;" is equivalent to these two lines: "returnval *= x; x -= 1;"
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Beginning in Computer Science

Postby segmentation fault » Fri Dec 21, 2007 7:28 pm UTC

thats not recursion.

if you are saying implement a loop instead of recursion, you are correct, since recursion will eat your call stack. by definition, a recursive function applies the function within itself.
Last edited by segmentation fault on Fri Dec 21, 2007 7:30 pm UTC, edited 1 time in total.
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 7:29 pm UTC

Yes it is. Indefinite loops are recursive.

Edit: So it's not the textbook definition of recursion, but it's much faster than the functional-recursive version, anyway. It's not a recursive definition but the processor definitely goes over the same code a certain number of times that depends on x, in the same way it would in the functional version. And a decent compiler might even be capable of inlining and compacting a recursive definition of the factorial function.

The moment you stop thinking about recursion as something special, the more easily you'll understand what it is, how to do it, and how to make it faster, as I did.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Beginning in Computer Science

Postby segmentation fault » Fri Dec 21, 2007 7:34 pm UTC

recursion:

Code: Select all

unsigned int factorial(unsigned int n) {
     if (n <= 1) return 1;
     return n * factorial(n-1);
 }


not recursion, but does the same thing in a loop, which is not recursion.

Code: Select all

unsigned int factorial(unsigned int n) {
     unsigned int result = 1;
     if (n <= 1) return 1;
     while (n--) result *= n;
     return result;
 }


to put it simply:
Recursion: see Recursion
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 7:41 pm UTC

Yet that doesn't take into account a compiler which may be able to optimize the two into a non-recursive function. Which means your definition of recursion is a little weak: name a recursive function that can't be transformed into a non-recursive function according to your definition.


I agree that if you're doing a CS class and they ask you to define recursion you should go with "a function that calls itself to arrive at its answer" but that's the boring, not very interesting form of recursion. I don't consider it particularly interesting at all when you can make virtually any function recursive or iterative. Whether one solution is more elegant than the other is more determined by the language and the tools it gives you than anything else.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Beginning in Computer Science

Postby segmentation fault » Fri Dec 21, 2007 7:46 pm UTC

Anpheus wrote:Yet that doesn't take into account a compiler which may be able to optimize the two into a non-recursive function. Which means your definition of recursion is a little weak: name a recursive function that can't be transformed into a non-recursive function according to your definition.


Ackermann (sp?) function REQUIRES recursion.

Anpheus wrote:I agree that if you're doing a CS class and they ask you to define recursion you should go with "a function that calls itself to arrive at its answer" but that's the boring, not very interesting form of recursion. I don't consider it particularly interesting at all when you can make virtually any function recursive or iterative. Whether one solution is more elegant than the other is more determined by the language and the tools it gives you than anything else.


if you are iterating over a tree (which is a root node that has trees as children), the code becomes more clear using recursion.
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Beginning in Computer Science

Postby Anpheus » Fri Dec 21, 2007 7:50 pm UTC

Ah, so you've mentioned the more computer sciency definition of recursion: there is a difference between primitive recursive functions and general recursive functions. One is a subset of the other and the Ackermann Function can't be defined iteratively because it's not primitive recursive.

That's all I wanted to point out.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Recursion

Postby segmentation fault » Fri Dec 21, 2007 8:41 pm UTC

the point is recursion and iteration are 2 different concepts. recursion requires a function to be put in terms of itself, and lacks the variable storage (total value, loop control variable etc.) of iteration via while/for.
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Recursion

Postby Anpheus » Fri Dec 21, 2007 8:43 pm UTC

The fact that the call stack exists at all tells us that there is a memory cost involved with recursing, and that merely because your code doesn't reference another, temporary variable doesn't mean one doesn't exist.

The actual cost of the recursive function is much more memory and much more time, so I fail to see how you can make an argument for iteration taking more memory in the form of variables.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
Hench
Porn, hence, Man
Posts: 498
Joined: Wed Mar 28, 2007 4:16 pm UTC
Location: Right between my eyes
Contact:

Re: Beginning in Computer Science

Postby Hench » Fri Dec 21, 2007 9:35 pm UTC

spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? M

I've written them enough to appreciate that there are times and places where recursion simplifies the method functionally and also conceptually. I've been coding professionally for about 6 months and casually for years on top of that and have found that recursion is most useful, especially when using a programming language that isn't imperative. In fact, now that I think about it, the basis for functional and logic programming languages is recursion. (If someone's willing to prove me wrong on this last bit, by all means, go ahead. I'm not an expert.)

If you want explicit examples of code where I've used recursion instead of imperative loops, I'll be more than happy to provide them.
Spoiler:
Your perceptions will not change reality, but simply color it.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Beginning in Computer Science

Postby btilly » Fri Dec 21, 2007 10:10 pm UTC

spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Don't get me wrong, every programmer worth his salt should understand recursion and be able to do it; I just don't use it a lot...

While I agree that you should not use recursion where you don't need to, I've used it plenty of times in production code in the wild.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
blob
Posts: 350
Joined: Thu Apr 05, 2007 8:19 pm UTC

Re: Beginning in Computer Science

Postby blob » Fri Dec 21, 2007 10:20 pm UTC

Any iterative function can be modeled using recursion. If your language optimizes tail calls (as does Scheme, Stackless Python and most functional languages) it needn't use up extra stack.

Any recursive function can be modeled using iteration, with an explicit stack if necessary. That's how recursion can be compiled to native code.

Continuations can model any control structure - iteration, recursion, goto, and faster than light travel. (Only with plus edition)

Monads can model continuations.

Haskell wins!
Avatar yoinked from Inverloch.

"Unless ... unless they kill us, then animate our corpses as dead zombies to fight for them. Then I suppose they've taken our lives, AND our freedom."
- Elan, OOTS 421.

spelunker
Posts: 102
Joined: Wed Dec 05, 2007 7:07 am UTC

Re: Beginning in Computer Science

Postby spelunker » Fri Dec 21, 2007 11:09 pm UTC

Hench wrote:
spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? M

I've written them enough to appreciate that there are times and places where recursion simplifies the method functionally and also conceptually. I've been coding professionally for about 6 months and casually for years on top of that and have found that recursion is most useful, especially when using a programming language that isn't imperative. In fact, now that I think about it, the basis for functional and logic programming languages is recursion. (If someone's willing to prove me wrong on this last bit, by all means, go ahead. I'm not an expert.)

If you want explicit examples of code where I've used recursion instead of imperative loops, I'll be more than happy to provide them.


Please, an example. Except for probably some special cases, I doubt recursion is ever an improvement over iteration. I mean, like has been mentioned, it makes tree traversal a lot easier, but other than that implementing something recursively just means you end up with a lot more function calls than you need, as well as possibly making the code harder to understand.

User avatar
wisnij
Posts: 426
Joined: Mon Jun 26, 2006 5:03 pm UTC
Location: a planet called Erp
Contact:

Re: Beginning in Computer Science

Postby wisnij » Fri Dec 21, 2007 11:17 pm UTC

spelunker wrote:Please, an example. Except for probably some special cases, I doubt recursion is ever an improvement over iteration. I mean, like has been mentioned, it makes tree traversal a lot easier, but other than that implementing something recursively just means you end up with a lot more function calls than you need, as well as possibly making the code harder to understand.

Recursive-descent parsing is something I have actually used in the past, several times in fact.
I burn the cheese. It does not burn me.

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Recursion

Postby segmentation fault » Fri Dec 21, 2007 11:29 pm UTC

Anpheus wrote:The actual cost of the recursive function is much more memory and much more time, so I fail to see how you can make an argument for iteration taking more memory in the form of variables.


im not.
people are like LDL cholesterol for the internet

Rysto
Posts: 1459
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Beginning in Computer Science

Postby Rysto » Sat Dec 22, 2007 12:13 am UTC

blob wrote:Any iterative function can be modeled using recursion. If your language optimizes tail calls (as does Scheme, Stackless Python and most functional languages) it needn't use up extra stack.

gcc does too, apparently. I was actually quite annoyed to learn this at the time, because instead of my program crashing due to a stack overflow it got stuck in an infinite loop instead, and it took me forever to figure out how I had introduced a "deadlock" into the code.

User avatar
Hangar
Posts: 171
Joined: Fri Nov 23, 2007 3:41 am UTC

Re: Recursion

Postby Hangar » Sat Dec 22, 2007 1:57 am UTC

That's a good reason to turn off optimizations in debug code. But yeah, most compiled languages will do proper tail recursion. You can assume it'll happen if you make it obvious enough (return a direct recursive call, without transforming the result in any way).

Simple recursion can be more natural when you want to say "try again." Say you're doing an input request, and you only want to take one correct result from the input.

Code: Select all

int askForInt()
{
   print "Gimme an int"
   string data = readInput()
   if (data isn't int)
      print "That wasn't an int."
      return askForInt()
   else
      return stringToInt(data)
}


Wheras iteratively, you'd have to put a loop in and only break out of the loop when you get the right result. That's kinda backwards. It makes more sense when you're applying a lot of transforms to the input before verifying it. The extra indentation that a loop requires will make your code less clear. And you can do the tail recursive call in the middle of a loop instead of at the end. Labels for control statements help deal with this problem, too.

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Recursion

Postby Anpheus » Sat Dec 22, 2007 2:17 am UTC

segmentation fault wrote:
Anpheus wrote:The actual cost of the recursive function is much more memory and much more time, so I fail to see how you can make an argument for iteration taking more memory in the form of variables.


im not.


You implied it with the statement about variable storage:

the point is recursion and iteration are 2 different concepts. recursion requires a function to be put in terms of itself, and lacks the variable storage (total value, loop control variable etc.) of iteration via while/for.


The two, with the exception of functions that are not primitive recursive but are general recursive, should be identical. That is, any primitive recursive function can be transformed into an iterative form, and vice-versa. The overhead of the stack is that extra storage space used by the recursive version that you don't see. It's still there, but the language has abstracted it away such that you don't have to deal with a call stack.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
TomBot
Posts: 228
Joined: Sun Jul 29, 2007 1:17 am UTC
Location: Illinois (UIUC)
Contact:

Re: Recursion

Postby TomBot » Sat Dec 22, 2007 6:43 am UTC

Hangar wrote:That's a good reason to turn off optimizations in debug code. But yeah, most compiled languages will do proper tail recursion. You can assume it'll happen if you make it obvious enough (return a direct recursive call, without transforming the result in any way).

Simple recursion can be more natural when you want to say "try again." Say you're doing an input request, and you only want to take one correct result from the input.

Code: Select all

int askForInt()
{
   print "Gimme an int"
   string data = readInput()
   if (data isn't int)
      print "That wasn't an int."
      return askForInt()
   else
      return stringToInt(data)
}


Wheras iteratively, you'd have to put a loop in and only break out of the loop when you get the right result. That's kinda backwards. It makes more sense when you're applying a lot of transforms to the input before verifying it. The extra indentation that a loop requires will make your code less clear. And you can do the tail recursive call in the middle of a loop instead of at the end. Labels for control statements help deal with this problem, too.


Just as a technical matter, I don't think that's a good idea. You end up with a possible bug that exhibits itself only when you don't optimize, namely that a user can crash the program by leaning on the enter key until it runs out of stack space. Heh, maybe use goto instead.

Recursion is mostly only useful for tree traversals, parsing, and the like. However, you still must learn it if you want to understand computers at all. Frankly I don't see what's so hard about it.

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Recursion

Postby Anpheus » Sat Dec 22, 2007 7:13 am UTC

As others have mentioned, if the compiler detects it, that code becomes iterative and will not pose a stack problem, but as you said, it would be a bad idea to do your debug and quality control with settings that you aren't using in production. IMO, the only difference between your debug and production settings should be added symbol information and whatever other extra information you can get out of the compiler and debugger, but nothing that significantly affects the machine code that results.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Recursion

Postby segmentation fault » Sat Dec 22, 2007 7:45 am UTC

Anpheus wrote:You implied it with the statement about variable storage:


which is not needed for recursion.

Anpheus wrote:The two, with the exception of functions that are not primitive recursive but are general recursive, should be identical.


because they achieve the same result does not mean they are the same.

Anpheus wrote:That is, any primitive recursive function can be transformed into an iterative form, and vice-versa.


ok, so theyre different then.

Anpheus wrote:The overhead of the stack is that extra storage space used by the recursive version that you don't see. It's still there, but the language has abstracted it away such that you don't have to deal with a call stack.


yes, i get it. compilers optimize away bad things in the same way it unrolls loops. but again, the 2 are fundamentally different concepts.
people are like LDL cholesterol for the internet

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Recursion

Postby Anpheus » Sat Dec 22, 2007 7:58 am UTC

A goto and a recursive call is fundamentally unique how? You can replace a goto with a recursive call, and since loops are just fancy built-in goto mechanisms with a few rules about their behavior already set, they can be turned into each other really easily.

There is extra variable storage or overhead with recursive calls that you just don't see because, well, you aren't thinking about the problem correctly.

Let's take a simple "addition" loop versus a recursive call using a function S.

Code: Select all

Loop:
//Add S to an integer X:
for (/* */; S > 0; S--)
    X++;

Recursive function:
//Add S to an integer X:
S(X,0) := X;
S(X,s) := 1 + S(X,s-1);


Where's the overhead? I see no variable allocation that differs in either case, in fact, one takes up a little more if not optimized to be iterative anyway, in addition to the fact that you have to actually have the code for a function there.

Let's take the factorial function now:

Code: Select all

Loop:
//Take the factorial of a number X:
for (int _i_ = 2; _i_ < X; _i_++)
    X *= _i_;

Recursive function:
//Take the factorial of a number X, from your code sample earlier
factorial(X) {
     if (_X_ <= 1) return 1;
     return _X_ * factorial(_X_-1);
}


The "extra variable storage" has underlines around it. See each use of underlines around X in the second function there? That's extra variable storage. Each time you call X, you instantiate a new X that is different from the old X, which takes up more space on the stack. It isn't until you reach X == 1 that you start popping those X's off the stack and multiplying things together.

The result is that your example will do, for X = 10:

Push 10
Push 9
Push 8
Push 7 ...

All of that on the stack. Do you see why recursive functions use up space that doesn't have to be?
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

photosinensis
Posts: 163
Joined: Wed Aug 22, 2007 6:17 am UTC

Re: Recursion

Postby photosinensis » Sat Dec 22, 2007 6:02 pm UTC

spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Don't get me wrong, every programmer worth his salt should understand recursion and be able to do it; I just don't use it a lot...


It's not always possible to write something iteratively, and even when it is, it's not always to your benefit to do so. For example, take the Tower of Hanoi. Here's the really simple recursive solution in pseudocode:

Code: Select all

hanoi(start, aux, dest, n)
{
    if n > 0
    {
        hanoi(start, dest, aux, n-1);
        move disk n to dest;
        hanoi(aux, start, dest, n-1);
    }
}


Doing it iteratively (through a series of for loops) is a pain in the ass and should not be tried. For more interesting variants of the problem, which my algorithms prof loved to include on tests, solving it iteratively might not only be a bad idea, but doing so might be impossible (we certainly didn't look into such problems, because the algorithm takes a lot longer to write out, and you have to deal with more disks than just the two). Generally, though, don't implement a recursion stack if you don't have to.

Another thing to take into account is trees. Traversing trees is possible iteratively, but it's not only easier to do recursively, it's more efficient. Fibonacci is actually one of the unusual (though certainly not rare) cases where defining the function recursively is retarded--taking a problem solvable in O(log n) time and doing so in O(2^n) time. In a majority of cases, you can actually get an improvement in efficiency by using recursion. Of course, you're not actually using any more memory to traverse a tree recursively, since you're only playing with pointers--you just need three pointers to do the job.

Furthermore, in functional programming (yay Lisp!), recursion is an absolute requirement. For() loops are done through tail recursion.

However, the simplest explanation of recursion has already been shown in this thread, through a link to the jargon file.
While I clicked my fav'rite bookmark, suddenly there came a warning,
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.

User avatar
Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

Re: Recursion

Postby Anpheus » Sat Dec 22, 2007 7:21 pm UTC

Absolutely, you bring up totally valid points where recursion sometimes is more efficient. But the efficiency comes at a space cost, the stack. Unless your compiler is efficient, in which case it transforms the solution into one that is essentially iterative, I mean, as far as the CPU is considered, a jmp is a jmp, whether part of a loop or a function. (I'm skipping over some details so please don't pedant me about long jmp and different calling styles and what-not.)
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Re: Recursion

Postby Govalant » Sat Dec 22, 2007 8:16 pm UTC

Although in some cases it might be a bad idea, it can prove itself to be very useful on ocasions.

In a game I was writing (A MMORPG, never finished), when got into a place with a roof, the roof (only of that place) needed to be erased. And I couldn't think of a way other than "dont draw current tile, check adjacents". A non-recursive algorithm would have probably been much more complicated.
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

User avatar
wisnij
Posts: 426
Joined: Mon Jun 26, 2006 5:03 pm UTC
Location: a planet called Erp
Contact:

Re: Recursion

Postby wisnij » Sat Dec 22, 2007 10:43 pm UTC

photosinensis wrote:Fibonacci is actually one of the unusual (though certainly not rare) cases where defining the function recursively is retarded--taking a problem solvable in O(log n) time and doing so in O(2^n) time.

Unless you cache the intermediate results. ;)
I burn the cheese. It does not burn me.

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Re: Recursion

Postby Govalant » Sat Dec 22, 2007 11:37 pm UTC

wisnij wrote:
photosinensis wrote:Fibonacci is actually one of the unusual (though certainly not rare) cases where defining the function recursively is retarded--taking a problem solvable in O(log n) time and doing so in O(2^n) time.

Unless you cache the intermediate results. ;)


If you're talking about getting the nth fibonacci number there's already a exact formula. It just uses integer powers and division by sqrt(5).
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

User avatar
Amnesiasoft
Posts: 2573
Joined: Tue May 15, 2007 4:28 am UTC
Location: Colorado
Contact:

Re: Recursion

Postby Amnesiasoft » Sat Dec 22, 2007 11:50 pm UTC

Govalant wrote:Although in some cases it might be a bad idea, it can prove itself to be very useful on ocasions.

In a game I was writing (A MMORPG, never finished), when got into a place with a roof, the roof (only of that place) needed to be erased. And I couldn't think of a way other than "dont draw current tile, check adjacents". A non-recursive algorithm would have probably been much more complicated.

Floodfill, and that's a pretty good one too, I'd hate to try to program that in iteratively.

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Beginning in Computer Science

Postby thoughtfully » Sun Dec 23, 2007 12:01 am UTC

Anpheus wrote:Recursion shouldn't be a mind freak, it's just an every day thing in an out of the ordinary circumstance. The problem is most students of programming to my knowledge thing programs are these very linear things that go from start to finish and may only once in a while loop over itself for a wee bit. That's not really very complex programming at all and it's poorly suited to a lot of problems. Really interesting programs start and end in multiple places and will recurse over themselves a lot.


Here, go to this website. When you get it, you'll know what recursion is:

Recursion at the Jargon File


This is amusing, but back when Norton/Symantec was still run by Peter Norton, I had an assembler reference by him that had this in the index in the back of the book. Wicked cool!

It might have been infinite loop instead. As anyone who has ever cheated and read the unix cookie database knows: to iterate is human, to recurse, divine!
Last edited by thoughtfully on Sun Dec 23, 2007 12:20 am UTC, edited 2 times in total.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Re: Recursion

Postby Govalant » Sun Dec 23, 2007 12:12 am UTC

Amnesiasoft wrote:
Govalant wrote:Although in some cases it might be a bad idea, it can prove itself to be very useful on ocasions.

In a game I was writing (A MMORPG, never finished), when got into a place with a roof, the roof (only of that place) needed to be erased. And I couldn't think of a way other than "dont draw current tile, check adjacents". A non-recursive algorithm would have probably been much more complicated.

Floodfill, and that's a pretty good one too, I'd hate to try to program that in iteratively.


They're pretty much the same :P
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Recursion

Postby btilly » Sun Dec 23, 2007 12:32 am UTC

Govalant wrote:
wisnij wrote:
photosinensis wrote:Fibonacci is actually one of the unusual (though certainly not rare) cases where defining the function recursively is retarded--taking a problem solvable in O(log n) time and doing so in O(2^n) time.

Unless you cache the intermediate results. ;)


If you're talking about getting the nth fibonacci number there's already a exact formula. It just uses integer powers and division by sqrt(5).

Calculating sqrt(5) to sufficient precision to give a precise answer is extremely difficult. The fastest solution that I know of for finding the exact integer value of the n'th Finbonacci number recursively uses the identities F2n = 2Fn+1Fn-Fn2, F2n+1 = Fn+12+Fn2, and F2n+2 = Fn+12+2Fn+1Fn. (I hope I worked those out correctly...) This allows one go to down by powers of two.

So, for instance, F25 would require (F12, F13). Which would require (F6. F7). Which would require (F3, F4). Which would require (F1, F2). Which are both 1.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.


Return to “Religious Wars”

Who is online

Users browsing this forum: No registered users and 3 guests