Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Geek Culture / What makes recursion useful?

Author
Message
Dark Java Dude 64
Community Leader
14
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 15th Aug 2012 14:46
I have heard before of the usefulness of recursion in programming, and I have heard about how the the Minecraft terrain generator uses it etc... I have researched and pondered over it for so long but I can't seem to figure out how it could be useful! Anyone have a good way to explain it to me? Thanks!

Your signature is being eras
bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 15th Aug 2012 15:08 Edited at: 15th Aug 2012 15:13
fractals are created with recursive mathematics, so obviously anything with fractals (like maps in minecraft) would be benefited with recursive function calls.

It can save a lot of lines of code and be more efficient in other things. For example, looping through a list of characters and removing spaces from the beginning. This can be done with only a couple lines. You take a string, check the first character, if it's a space, get rid of it then call the same function again. If there's no space, return from the function. This use is probably really inefficient compared to using, say, a while loop and jumping out when done, but it's a simple example.

Hodgey
15
Years of Service
User Offline
Joined: 10th Oct 2009
Location: Australia
Posted: 15th Aug 2012 16:03
The Merge-sort uses recursion and it can be quite fast.

Sometimes it feels more intuitive to use recursion (even though it might be slower than iteration). I wrote a program to find all solutions to the 8 Queens problem which utilized recursion. I haven't done any time analysis on it and iteration might be faster but at the time of writing the code, recursion felt like the right way to go.

Diggsey
19
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 15th Aug 2012 17:00
Recursion doesn't help with efficiency - a non-recursive solution can always be at least as fast as a recursive one - but it can really help with readability. Often a recursive solution is easy to write down without having to really think deeply about it, whereas working out a non-recursive one can take quite a bit of effort. In addition, good compilers can use optimisation techniques such as tail recursion optimisation to make the recursive code be no less efficient than the non-recursive version.

[b]
MrValentine
AGK Backer
14
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 15th Aug 2012 19:06
I don not follow... Is there a wiki on This?

swissolo
15
Years of Service
User Offline
Joined: 9th Jan 2010
Location:
Posted: 15th Aug 2012 19:34 Edited at: 15th Aug 2012 19:35
The first example I can think of off the top of my head is a fill tool(image editting). It's pretty simple to recusively check the various pixels around a newly filled point, then repeating for the next new point, eventually reaching all the boundaries.

swis
Joined: Tue Dec 16th 2008
Interstellar
Neuro Fuzzy
17
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 15th Aug 2012 21:38
It's just an easier way to think about objects. Quadtrees and qsort and file parsing (like for xml) are where I've used them before.

TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 12:53 Edited at: 16th Aug 2012 12:54
Recursion has one huge setback: Stack size.

I wrote a flood fill function in DBP for Lightship using recursion, and I got a stack overflow when trying to flood huge maps.

This is of course dependant on what programming language you're using. For instance, LUA and python have a really small stack size so there's no way you can write any recursive functions using those languages.

For those that don't know what recursion is, here's the most basic form (this will crash your program):



TheComet

Your mod has been erased by a signature, please reduce him [overall] to no larger than 120 kg please.
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 13:30 Edited at: 16th Aug 2012 13:31
It could be that the Endfunction link is stored, so if you call it from outside the loop it probably wouldn't overflow. I know that Return is stored, and Endfunction is pretty much the same as Return.

TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 13:35
And that's what the stack is for, hence "stack overflow" when you call too many functions without ending them.

TheComet

Your mod has been erased by a signature, please reduce him [overall] to no larger than 120 kg please.
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 13:37 Edited at: 16th Aug 2012 13:38
Quote: "And that's what the stack is for, hence "stack overflow" when you call too many functions without ending them."


Yeah, but recursion can be outside the function, it's still recursion so long as you are repeatedly calling the function.

Hodgey
15
Years of Service
User Offline
Joined: 10th Oct 2009
Location: Australia
Posted: 16th Aug 2012 13:40
Quote: "Yeah, but recursion can be outside the function,"

Doesn't that defeat the purpose of recursion?

Is there a way to tell if you're getting close to a stack overflow so you can return before it gets there?

bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 13:41
Well no usually you call the same function within the function over and over, so if you do it too much you can overflow. If you just call the same function over and over in like a loop, that's not really recursion, that's just a loop.

Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 13:43
Surely this is the same with no stack overflow?
Do
Recursion()
loop
end

function Recursion()
inc a
endfunction

Hodgey
15
Years of Service
User Offline
Joined: 10th Oct 2009
Location: Australia
Posted: 16th Aug 2012 13:51
Pincho, that's just looping through a function. Here's a classic example of recursion...the factorial.



Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 13:59 Edited at: 16th Aug 2012 14:02
Oh, well I would never use a program that increases my stack size.

bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 14:07
well the way around that is to keep a running total of how much you've called it. For example, if you know you'll never want to call the same function more than 100 times, you just keep a tally and exit out if you hit the limit.

Plystire
22
Years of Service
User Offline
Joined: 18th Feb 2003
Location: Staring into the digital ether
Posted: 16th Aug 2012 14:08
The function being called multiple times is not what makes it recursive. Definition of recursion: "The act of returning to or running back". Basically recursive functions are ones that, when finished, must "return to" the starting point.

One of my favorite examples of a recursive function is one used to generate a classic maze.



All the function does is flag a cell in the maze as filled, then if it can step in a direction (without hitting another filled cell) it will call itself with the new coordinates. When it comes to a point where there are no available spots to move to it will end the function, recursing back to the previous position and checking for more available places to move to.
The maze is fully generated when the function has fully recursed and subsequently ended. So to generate the maze, you need only say "genMaze(randomX, randomY)"


~Plystire

A rose is only a rose until it is held and cherished -- then it becomes a treasure.
Zotoaster
20
Years of Service
User Offline
Joined: 20th Dec 2004
Location: Scotland
Posted: 16th Aug 2012 14:45
Quote: "Oh, well I would never use a program that increases my stack size."


Every time you call a function it adds it to the stack, even if it's not recursive. The thing about recursion is that it keeps on adding to the stack, hence the stack overflow. All recursive functions need an 'exit condition' to avoid this.

"everyone forgets a semi-colon sometimes." - Phaelax
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 14:51
Quote: "Every time you call a function it adds it to the stack, even if it's not recursive. The thing about recursion is that it keeps on adding to the stack, hence the stack overflow. All recursive functions need an 'exit condition' to avoid this."


Exit after repeated calls probably only saves 1 ExitFunction not all of them. Like this...



Dark Java Dude 64
Community Leader
14
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 16th Aug 2012 15:15
Hmm... Im still not getting why recursion is better over a function call in a loop. I'll look at the thread in better detail later today.

Your signature is being eras
bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 15:19
if you don't understand recursion than you probably don't understand recursion.

Dark Java Dude 64
Community Leader
14
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 16th Aug 2012 15:33
I understand THAT part of it. Just don't understand how it's useful. Nice phrase you got there, though.

Your signature is being eras
bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 15:36
Well try programming that maze routine without it

Zotoaster
20
Years of Service
User Offline
Joined: 20th Dec 2004
Location: Scotland
Posted: 16th Aug 2012 16:10 Edited at: 16th Aug 2012 16:14
To put it simply, recursion is just a different way of thinking. Sometimes the big picture looks the same as the parts that make it. Again, think fractals. If you can organise something like that, you've drastically simplified your workload.

Let me use Sparky's collision as an example. Ever wonder why it's so much better than DBP's built-in intersect object command? Because it creates a high level abstraction to simplify it's work, and using recursion simplifies everything. What it does is that it puts an imaginary box around an object. If your ray doesn't intersect that box, it doesn't intersect the object, so don't bother checking the triangles. Now comes the recursive part. It splits that box into two sub-boxes, and each of those into two further sub-boxes, etc, until it reaches a certain number of vertices per box (2 by default). This is basically a tree structure, and recursion and trees work well together. Now, apply the same technique used with the whole-box to each of the sub-boxes. In other words, if the box on the front half of an object is intersected but not the back half, ignore all the sub-boxes in the back and continue recurring through the front half, doing the same to each of it's sub-boxes. It does this until it builds a linear list of terminal boxes (boxes at the very end of the tree, with no child-boxes) that the ray intersects, and for each of those only has to check intersections with the triangles inside them. That means for an object with say, 10,000 triangles, DBP's intersect object would have to do 10,000 checks, whereas Sparky's would only have to do about 20 or so.

"everyone forgets a semi-colon sometimes." - Phaelax
TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 17:26
Quote: "Exit after repeated calls probably only saves 1 ExitFunction not all of them. Like this..."


What do you mean? Exitfunctions end the function as well, you won't increase the stack size.

As Jerico said, read my signature.

TheComet

"if you don't understand recursion than you probably don't understand recursion." ~Jerico2day
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 18:12 Edited at: 16th Aug 2012 18:17
Quote: "What do you mean? Exitfunctions end the function as well, you won't increase the stack size."


You have to exit it for every time you call it, so if you call it 100 times in the loop you have increased the stack 100 times, and if you then exit, you are still on 99 stacks. So Exit only saves you 1 stack quantity. You are building up the ExitFunction address. Well that's what VB does anyway.

bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 18:44
Right, but when you exit, you go back to the line you were on just after you call the function. So something like this:

function rec(count)
if count => 100 then exitfunction count
count = rec(count + 1)
exitfunction count
endfunction

will call the function 100 times, and will exitfunction 100 times.

bringing the stack from 0 to 100 back to 0.

Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 18:51
Ok but how is that faster than the Do Loop version?

BiggAdd
Retired Moderator
20
Years of Service
User Offline
Joined: 6th Aug 2004
Location: != null
Posted: 16th Aug 2012 19:10
Quote: "Ok but how is that faster than the Do Loop version?"


Its not about being faster, its about personal preference.
Some things are easier to implement with recursion, some are easier to implement with loops.

Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 19:12 Edited at: 16th Aug 2012 19:14
Quote: "Its not about being faster, its about personal preference."


Oh, when TheComet said he used it for a fill, I thought he was trying to get more speed. Then I said, I wouldn't want to use up the stack, then somebody said exit all of the recursions, and then you are back to a loop. So it seems a waste of time to me. I use subroutines, and loops.

bitJericho
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 16th Aug 2012 19:18
Pincho, there's absolutely nothing wrong with that.

The point is, in cases where you know you won't overflow the stack, using recursion can make the code much, much more manageable. It could save you tons of code and quite frankly, I've found instances where recursion techniques were the only way I could think of the solution, where a normal do/loop was too complex for me to visualize and program properly. Sure, that makes me maybe not the best programmer alive, but it could mean the difference between completing a bit of bug-free programming or leaving it on the backburner.

Dazzag
22
Years of Service
User Offline
Joined: 26th Aug 2002
Location: Cyprus
Posted: 16th Aug 2012 19:20
At work (*many* years ago) we once wrote an XML parser in an *ancient* Unix language to decode XML messages from basically an airline GDS system. Forget speed and the like, we just wouldn't have been able to program it within the allocated time (ie. money) without using recursion. Right lot of hair pulling that one...

Oh and we used recursive call routines. ie. a called program to decode an XML message would call itself for sections of the XML message. Which would then call itself for smaller sections etc etc. Stack size was obviously a problem ("call stack" in the language we used) but we allocated enough session memory (probably as much as a stupidely high 1mb!!!!) to handle the biggest message we could find from the airline system (loads of messages).

A decade later I made a much more efficient version (we made it too generic at the time) that didn't use recursion but hey ho it was a decade later and our backs were against the wall at the time (I designed it, I didn't actually write the original code, just advised on it).

Cheers

Current fave quote : Cause you like musicians and I like people with boobs.
ionstream
20
Years of Service
User Offline
Joined: 4th Jul 2004
Location: Overweb
Posted: 16th Aug 2012 19:44
Recursive functions are useful for use on recursive structures, like trees. Imagine trying to get all of the files in a particular directory, going into each subdirectory. On the high level, you might think to yourself "add each file to an array, and for each folder add those files to the array as well". A recursive function allows you to write just that:



Although you could write this in a non-recursive function, you would have to use a stack anyways to keep track of what folder you are currently in and where you just came from, so there would be no memory or speed improvements. Just make sure you don't follow symbolic links!

Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 19:50
Quote: "The point is, in cases where you know you won't overflow the stack, using recursion can make the code much, much more manageable."


Ok, but when you can't imagine something, I get the opposite, and I can imagine the computer wasting memory, and that gives me OSD.

TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 20:02 Edited at: 16th Aug 2012 20:05
A funny thing that happened to me at work when I had to program a micro controller, I used a recursive function for an algorithm and it wrote so much data to the stack that it started overflowing into the rest of the memory. First it erased all of the RAM, then it erased the CPU registers and finally even overwrote the ROM.

Moral of the story? Use this against Seppuku's doom machine.

[EDIT]

Quote: "fractals are created with recursive mathematics"


Computer programs don't use recursive functions in this sense though to generate fractals, otherwise your stack pointer will be blasted into oblivion.

TheComet

"if you don't understand recursion than you probably don't understand recursion." ~Jerico2day
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 20:18
Quote: "Computer programs don't use recursive functions in this sense though to generate fractals, otherwise your stack pointer will be blasted into oblivion."


No, people are saying that recursion can clear the stack, but your method, the fast method, doesn't. And that's why you are confusing me. You are only mentioning the version that doesn't clear the stack.

Diggsey
19
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 16th Aug 2012 20:25 Edited at: 16th Aug 2012 20:27
Recursion always clears the stack. The only danger of using recursion is doing a recursion too deep, in which case a stack overflow is possible. However, as long as you don't overflow the stack the functions will all return and so clear the stack to its original state.

[b]
swissolo
15
Years of Service
User Offline
Joined: 9th Jan 2010
Location:
Posted: 16th Aug 2012 20:33 Edited at: 16th Aug 2012 20:34
Quote: "No, people are saying that recursion can clear the stack, but your method, the fast method, doesn't. And that's why you are confusing me. You are only mentioning the version that doesn't clear the stack."

The stack is cleared when the recursion is completed(or at least as pieces of the recursion are completed) You can still dig too deep as Diggsey says above me.

swis
Joined: Tue Dec 16th 2008
Interstellar
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 20:38 Edited at: 16th Aug 2012 20:41
Well I don't like recursion, and will never use it anyway.

Libervurto
18
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 16th Aug 2012 21:05 Edited at: 16th Aug 2012 22:05
I adapted this program from example I found in a C++ book. It's a really nice example of recursive problem solving.


This code is old so I'll go through it and see if I can make improvements.

[edit]
See below for the improved version:

I like how I optimised the initialisation of the puzzle: got rid of those nasty repeat loops and only use one call of rnd(); much more efficient.

Shh... you're pretty.
The Weeping Corpse
13
Years of Service
User Offline
Joined: 19th Sep 2011
Location: United Kingdom
Posted: 16th Aug 2012 21:19
Recursion is useful for things such as sorting and searching.

for example when searching a tree structure it makes sense to have one function that can explore the trunk, then the branches owned by the trunk, and the child of the branch (leafs or maybe othe brances).

It would be silly to code seperate functions for trunks, branches and leafs.

TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 21:47
Quote: "but your method, the fast method, doesn't. And that's why you are confusing me. You are only mentioning the version that doesn't clear the stack."


You are incredibly confusing to me. Do you even read what I post?

Where did I mention "the fast method"? I posted a code example with recursion, and everywhere else I only talked about recursion and the resulting disadvantages (except for that very last comment which wasn't even directed at you anyway, I was pointing out that fractal calculations are recursive, but use the do-loop method because the stack wouldn't be able to handle it if it were calculated using recursive functions).

The do-loop method doesn't have to clear the stack because it never uses the stack in the first place.

TheComet

"if you don't understand recursion than you probably don't understand recursion." ~Jerico2day
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 21:55 Edited at: 16th Aug 2012 21:57
Quote: "Where did I mention "the fast method"?"


Some people said to count the iterations, and clear the stack. Being as you don't do that, it is the fast method, not top clear the stack in chunks. So your way doesn't count the iterations, and doesn't clear the stack. That makes it faster. So it is the fast method. You just let the stack overflow.

the_winch
22
Years of Service
User Offline
Joined: 1st Feb 2003
Location: Oxford, UK
Posted: 16th Aug 2012 21:57
It's all answered in this thread.

By way of demonstration, he emitted a batlike squeak that was indeed bothersome.
Libervurto
18
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 16th Aug 2012 21:59
Here's a better version of the Towers of Hanoi:


Amazing that only 23 lines of code are actually working on solving the problem.

Shh... you're pretty.
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 22:28
Yeah, well solve this in a few lines, it's a nightmare. I just finished it.



TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 22:30
Quote: "Some people said to count the iterations, and clear the stack. Being as you don't do that, it is the fast method, not top clear the stack in chunks. So your way doesn't count the iterations, and doesn't clear the stack. That makes it faster. So it is the fast method. You just let the stack overflow."


Oh, my flood fill function? It does clear the stack when it's finished. The reason it overflows is because, as someone said:

Quote: "Recursion always clears the stack. The only danger of using recursion is doing a recursion too deep, in which case a stack overflow is possible. However, as long as you don't overflow the stack the functions will all return and so clear the stack to its original state."


TheComet

"if you don't understand recursion than you probably don't understand recursion." ~Jerico2day
Pincho Paxton
22
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Aug 2012 22:42 Edited at: 16th Aug 2012 22:45
Oh I see, you do clear the stack. It was your first example that threw me.



I thought you were running a fill routine until the stack ran out.

TheComet
17
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Aug 2012 22:51
Sorry for the confusion, that's NOT how to do recursion (but that is the simplest example showing what recursion is).

TheComet

"if you don't understand recursion than you probably don't understand recursion." ~Jerico2day

Login to post a reply

Server time is: 2025-05-19 05:53:04
Your offset time is: 2025-05-19 05:53:04