Useful applications of recursion?
Moderators: phlip, Moderators General, Prelates

 Posts: 1129
 Joined: Thu Dec 10, 2009 6:21 pm UTC
 Location: Placerville, CA
 Contact:
Useful applications of recursion?
I was thinking today about this, partly from marveling over the (non)performance of a naivelyimplemented Fibonaccisequence function I did as I'm learning my way around Lisp, and partly from thinking about a recent job interview  what are some actually useful applications for recursive functions?
Because all I've seen, both in college and in job interviews, is stuff like "how would you write a function to calculate a given Fibonaccisequence number, hint, use recursion, we really want you to use recursion here, hint hint." But the thing is, I didn't even have to think about it for long to realize why my Fibonacci function was taking several seconds to get to even the 30th number on a multigigaherz computer  naive, stateless recursion is just about the least effective algorithm you could possibly choose for this problem (barring some kind of "loop through every possible value and test whether it's a valid Fibonacci number" approach, which is so perverse that I have to believe someone has deployed it in a production environment,) since every recursion has to drill all the way down to 1 twice! I don't know exactly what that is, but I think we can safely call it O(appalling)  whereas a straightforward loop algorithm is O(n) and takes only a couple numbers' worth of temporary storage.
And, y'know, that's one thing in a college course, where they just want to make sure you understand how recursion works (although it's still not a very good, since they never seem to get around to explaining when you would actually want to use it,) and the simplicity of it is kind of beautiful, but in practical terms it's friggin' ridiculous. (Recursivefactorial is another popular one, that's less absurd since it's still O(n), but when you get down to an effectiveperformance level a straight loop is still going to beat it just from not requiring n consecutive function calls, and is no more complex.) But in a job interview? And it was clear from the way they phrased it that the recursive solution was the "correct" answer  and, of course, I can say "sure, here's how you'd do that," but I keep wanting to preface it with "well, that wouldn't be my first choice..."
But I don't want to dismiss it outofhand. Recursion seems like something that probably does have genuinely useful applications  I just have no idea what they are. Anybody?
Because all I've seen, both in college and in job interviews, is stuff like "how would you write a function to calculate a given Fibonaccisequence number, hint, use recursion, we really want you to use recursion here, hint hint." But the thing is, I didn't even have to think about it for long to realize why my Fibonacci function was taking several seconds to get to even the 30th number on a multigigaherz computer  naive, stateless recursion is just about the least effective algorithm you could possibly choose for this problem (barring some kind of "loop through every possible value and test whether it's a valid Fibonacci number" approach, which is so perverse that I have to believe someone has deployed it in a production environment,) since every recursion has to drill all the way down to 1 twice! I don't know exactly what that is, but I think we can safely call it O(appalling)  whereas a straightforward loop algorithm is O(n) and takes only a couple numbers' worth of temporary storage.
And, y'know, that's one thing in a college course, where they just want to make sure you understand how recursion works (although it's still not a very good, since they never seem to get around to explaining when you would actually want to use it,) and the simplicity of it is kind of beautiful, but in practical terms it's friggin' ridiculous. (Recursivefactorial is another popular one, that's less absurd since it's still O(n), but when you get down to an effectiveperformance level a straight loop is still going to beat it just from not requiring n consecutive function calls, and is no more complex.) But in a job interview? And it was clear from the way they phrased it that the recursive solution was the "correct" answer  and, of course, I can say "sure, here's how you'd do that," but I keep wanting to preface it with "well, that wouldn't be my first choice..."
But I don't want to dismiss it outofhand. Recursion seems like something that probably does have genuinely useful applications  I just have no idea what they are. Anybody?
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
 Bjarne Stroustrup
www.commodorejohn.com  in case you were wondering, which you probably weren't.
 Bjarne Stroustrup
www.commodorejohn.com  in case you were wondering, which you probably weren't.
Re: Useful applications of recursion?
Recursion is useful when you want to recurse into treelike structure, eg. if you want to check if there is an element of the tree named "foo", you might have
Alternatively, when writing GUI programs, widgets are often nested one inside another. Then you can use a recursion to show all widgets.
Code: Select all
def check(node):
if node.name == "foo":
return True
for child in node:
if check(child):
return True
return False
Alternatively, when writing GUI programs, widgets are often nested one inside another. Then you can use a recursion to show all widgets.
Code: Select all
def show_all(widget):
widget.show()
for child in widget.get_children():
show_all(child)
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Useful applications of recursion?
I'd say mergesort is a pretty good example. I keeps the recursion depth at loglength depth at any one time, so you don't pile up the overhead, and its O(n log(n)). If most languages didn't come with a prepacked sort, it would be one of the first things a lot of folks would write.
Also, here's an efficient fib that uses recursion
forums.xkcd.com/viewtopic.php?f=12&t=79102&p=3721672
Also, here's an efficient fib that uses recursion
forums.xkcd.com/viewtopic.php?f=12&t=79102&p=3721672
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Useful applications of recursion?
commodorejohn wrote:But the thing is, I didn't even have to think about it for long to realize why my Fibonacci function was taking several seconds to get to even the 30th number on a multigigaherz computer  naive, stateless recursion is just about the least effective algorithm you could possibly choose for this problem (barring some kind of "loop through every possible value and test whether it's a valid Fibonacci number" approach, which is so perverse that I have to believe someone has deployed it in a production environment,) since every recursion has to drill all the way down to 1 twice! I don't know exactly what that is, but I think we can safely call it O(appalling)  whereas a straightforward loop algorithm is O(n) and takes only a couple numbers' worth of temporary storage.
That's because of imperative programming. If your language of choice automatically caches results (which it can, because it's a pure function), the recursive notation of the function becomes an O(n) loop too.
As far as I can imagine, actual recursion is often avoided in libraries to avoid stack overflows and because the calls are pretty expensive, but the correctness proof and, sometimes, notation is done in a recursive way. Like you said, for its elegance.
ETA: And of course recursive datastructures are recursive in their nature. You may write the methods for those structures any way you like, but the structure itself will be recursive in the end.
Re: Useful applications of recursion?
these seem like pretty good uses of recursion to me...
Code: Select all
makeFibs :: (Integer, Integer) > [Integer]
makeFibs (a, b) = let f@(_:t) = makeFibs (a, b)
in a : b : zipWith (+) f t
twoFibs :: Integer > (Integer, Integer)
twoFibs 0 = (1, 0)
twoFibs n = let (q, r) = divMod n 2
(a, b) = twoFibs q
x = a * a + b * b
y = 2 * a * b + b * b
in case r of
0 > (x, y)
1 > (y, x + y)
fibsFrom = makeFibs . twoFibs . succ
Code: Select all
import Control.Arrow
import Data.List
import Data.Numbers.Primes
bitCount 0 = 0
bitCount n = uncurry (+) . first bitCount $ divMod n 2
swing n  n < 33 = genericIndex smallOddSwing n
 True = product pList
where smallOddSwing = [1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195]
pListA q p prime = let x = div q prime in case x of
0 > case p of
1 > []
_ > [p]
_ > pListA x (p * prime ^ (mod x 2)) prime
pListB = (filter ((1==) . flip mod 2 . div n) . takeWhile (<= div n 3) $ dropWhile ((<= n) . (^2)) primes)
pListC = takeWhile (<= n) $ dropWhile (<= div n 2) primes
pList = (concatMap (pListA n 1) . takeWhile ((n >=) . (^2)) $ tail primes) ++ pListB ++ pListC
recFactorial n  n < 2 = 1
 True = (recFactorial $ div n 2) ^ 2 * swing n
factorial n  n < 20 = product [2..n]
 True = recFactorial n * 2 ^ (n  bitCount n)
Last edited by hotaru on Mon Jun 01, 2015 6:10 am UTC, edited 1 time in total.
Code: Select all
factorial = product . enumFromTo 1
isPrime n = factorial (n  1) `mod` n == n  1

 Posts: 207
 Joined: Thu May 19, 2011 4:28 pm UTC
 Location: Waterloo, Ontario
Re: Useful applications of recursion?
From an interview perspective, I think most people find the recursive solution (I liked the word 'notation' above) to be a bit easier to read and discuss, whereas other approaches within dynamic programming sometimes are not (as a matter of preference, of course)?
There's also the part where most 'programmers' are bad, and so just because they're interviewing you doesn't mean you shouldn't be interviewing them.
When I interview candidates, I usually ask them about a nonrecursive solution (even as just a talking point, like, do you know that bottomup is a thing?) or even the obviousbutstillstumps90%ofcandidates, "Would this recursive (Java, C#, etc.) solution have any problem with very large size inputs?" or something to that effect, and they usually reply with something unrelated and then have to be asked, "But do you think it would cause a stack overflow?" and then they usually tell me that no, the program does not access any web pages and I move on.
There's also the part where most 'programmers' are bad, and so just because they're interviewing you doesn't mean you shouldn't be interviewing them.
When I interview candidates, I usually ask them about a nonrecursive solution (even as just a talking point, like, do you know that bottomup is a thing?) or even the obviousbutstillstumps90%ofcandidates, "Would this recursive (Java, C#, etc.) solution have any problem with very large size inputs?" or something to that effect, and they usually reply with something unrelated and then have to be asked, "But do you think it would cause a stack overflow?" and then they usually tell me that no, the program does not access any web pages and I move on.

 Posts: 207
 Joined: Thu May 19, 2011 4:28 pm UTC
 Location: Waterloo, Ontario
Re: Useful applications of recursion?
And recursive data structures can still be dealt with via loops and stacks/queues... it's a matter of what constraints (i.e. memory/storage) are placed on the solution, no?
And in certain imperative cases, TCO is legit?
And in certain imperative cases, TCO is legit?
Re: Useful applications of recursion?
Yes, they can, but (at least IMO) doing so is often a PITA and makes for far less clear code than the recursive version. If your inputs are enough to cause stack overflows with a recursive solution (I have seen this happen once legitimately), I think the usual fix should be to allow for a larger stack vs go turn your algorithm insideout.DaveInsurgent wrote:And recursive data structures can still be dealt with via loops and stacks/queues... it's a matter of what constraints (i.e. memory/storage) are placed on the solution, no?
Anyway, I don't have much to add  my three "where do you use recursion" answers are (1) in a functional language, (2) trees, and (3) divideandconquer algs like mergesort & quicksort. Edit: oh: recursivedescent parsers.
Re: Useful applications of recursion?
DaveInsurgent wrote:then they usually tell me that no, the program does not access any web pages and I move on.
Haha, great.
Do you sometimes give them the contact details of a competitor's recruiter?

 Posts: 207
 Joined: Thu May 19, 2011 4:28 pm UTC
 Location: Waterloo, Ontario
Re: Useful applications of recursion?
EvanED wrote:Yes, they can, but (at least IMO) doing so is often a PITA and makes for far less clear code than the recursive version. If your inputs are enough to cause stack overflows with a recursive solution (I have seen this happen once legitimately), I think the usual fix should be to allow for a larger stack vs go turn your algorithm insideout.DaveInsurgent wrote:And recursive data structures can still be dealt with via loops and stacks/queues... it's a matter of what constraints (i.e. memory/storage) are placed on the solution, no?
Anyway, I don't have much to add  my three "where do you use recursion" answers are (1) in a functional language, (2) trees, and (3) divideandconquer algs like mergesort & quicksort. Edit: oh: recursivedescent parsers.
For sure  though, I think in Java you can blow the stack in as few as ~1000 recursions, and while you're right that you can just pump that stack size up, then you have a lot of memory if you use a lot of threads. I'm not disagreeing with you, but often when writing libraries you don't want to impose on the consumer certain assumptions.
Then again, I've also *never* written an "algorithm" in the better part of a decade as a senior developer. Not to derail the convo, but there are *way* more pressing things to deal with in web apps for average joe developer and it irks me that interviews (and interviewers) gets so carried away with "algorithm trivia". If I'm forced in to that kind of interview (because say it's a different team/dept. doing the hiring) I like to at least hear candidates be aware that there are nonrecursive ways to do things.
Flumble wrote:Do you sometimes give them the contact details of a competitor's recruiter?
That's a brilliant idea, but alas I think they tend to just go to startups where being able to say Docker Cloud Microservices!!!! gets you 150k+
Re: Useful applications of recursion?
As mentioned, recursion is extremely useful when working with recursive datastructures like trees and graphs. It's also essential to a lot of divide and conquer algorithms. Stack overflows aren't really a concern unless unless you go overboard using recursion where trivial loops would work just as well.
But now you're using O(N) memory (for the naive fibonacci function with memoization), when there's a trivial O(N) time, O(1) memory solution.
Although as that mind blowing algorithms thread showed, there are even faster algorithms that achieve O(log N) time and memory with recursion and memoization.
If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
Why would it ever not be legit? TCO has no effect on result, side effects, or order of execution of a function. It's an entirely safe optimization. The main argument against it (the only one that I'm aware of) is that by optimizing out the call stack it makes errors more difficult to debug, because you don't have a real stack trace anymore.
Flumble wrote:That's because of imperative programming. If your language of choice automatically caches results (which it can, because it's a pure function), the recursive notation of the function becomes an O(n) loop too.
But now you're using O(N) memory (for the naive fibonacci function with memoization), when there's a trivial O(N) time, O(1) memory solution.
Although as that mind blowing algorithms thread showed, there are even faster algorithms that achieve O(log N) time and memory with recursion and memoization.
DaveInsurgent wrote:And recursive data structures can still be dealt with via loops and stacks/queues... it's a matter of what constraints (i.e. memory/storage) are placed on the solution, no?
If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
And in certain imperative cases, TCO is legit?
Why would it ever not be legit? TCO has no effect on result, side effects, or order of execution of a function. It's an entirely safe optimization. The main argument against it (the only one that I'm aware of) is that by optimizing out the call stack it makes errors more difficult to debug, because you don't have a real stack trace anymore.

 Posts: 207
 Joined: Thu May 19, 2011 4:28 pm UTC
 Location: Waterloo, Ontario
Re: Useful applications of recursion?
If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
I thought the point was to work in the heap instead of on the stack, again all depending on what the environment the program is running in is.. "oh shit we need to add more system memory" is a problem that can be solved without recompiling a binary.
Why would it ever not be legit? TCO has no effect on result, side effects, or order of execution of a function. It's an entirely safe optimization. The main argument against it (the only one that I'm aware of) is that by optimizing out the call stack it makes errors more difficult to debug, because you don't have a real stack trace anymore.
I meant something that can be legitimately used but it's not always available (thanks, Java, C#, etc.)
Re: Useful applications of recursion?
Derek wrote:And in certain imperative cases, TCO is legit?
Why would it ever not be legit? TCO has no effect on result, side effects, or order of execution of a function. It's an entirely safe optimization. The main argument against it (the only one that I'm aware of) is that by optimizing out the call stack it makes errors more difficult to debug, because you don't have a real stack trace anymore.
there's the argument against it in JavaScript, which is that it would break the ability to access (and call functions from) the call stack through arguments.callee.caller(.caller.caller.caller...). I don't think it's a good argument, but it's the only reason that JavaScript implementations don't do TCO.
Code: Select all
factorial = product . enumFromTo 1
isPrime n = factorial (n  1) `mod` n == n  1
Re: Useful applications of recursion?
Topological sort on a directed acyclic graph. Also, finding articulation points in a graph.
The incredibly clever linear time findthemedian algorithm.
Finding a winning strategy in a twoplayer game.
The hashlife algorithm, Fast Fourier Transform, Strassen's matrix multiplication algorithm, ...
The incredibly clever linear time findthemedian algorithm.
Finding a winning strategy in a twoplayer game.
The hashlife algorithm, Fast Fourier Transform, Strassen's matrix multiplication algorithm, ...
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
Re: Useful applications of recursion?
Derek wrote:If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
I'm having a lot of difficulty envisioning a scenario where allocating from the heap would ever be faster than allocating from the call stack. I don't think that it's possible.
The only reason to use the heap rather than the stack would be if you're worried that the recursive calls would be deep enough to blow the stack.
Re: Useful applications of recursion?
Rysto wrote:Derek wrote:If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
I'm having a lot of difficulty envisioning a scenario where allocating from the heap would ever be faster than allocating from the call stack. I don't think that it's possible.
The only reason to use the heap rather than the stack would be if you're worried that the recursive calls would be deep enough to blow the stack.
In many cases, using loops may result in no extra allocation, and not only that but function calls are more expensive than jumps.
Summum ius, summa iniuria.
Re: Useful applications of recursion?
Rysto wrote:Derek wrote:If you're replacing recursion with a loop and a stack, all you've done is reinvented the call stack. There's no good reason to do this unless performance is absolutely essential.
I'm having a lot of difficulty envisioning a scenario where allocating from the heap would ever be faster than allocating from the call stack. I don't think that it's possible.
The only reason to use the heap rather than the stack would be if you're worried that the recursive calls would be deep enough to blow the stack.
If the overhead of recursive function calls dominates the runtime, or if the callstack contains a lot of extra data that is not needed for the recursive call. You can imagine a scenario where every stack frame requires several kilobytes of data, but only a single int result needs to be kept available on the stack. It's an unlikely scenario, but not impossible. But this should never be done unless there is a demonstrated need for the optimization.
Re: Useful applications of recursion?
Ooh, interesting. Do you know of a clear explanation of this algorithm? Googling just found me basically a powerpoint explanation that looks more confusing than a 500 character oneline perl program. (Okay, so I'm exaggerating.)notzeb wrote:The incredibly clever linear time findthemedian algorithm.
As far as recursion goes, I am with the OP on recursive fibonacci. However, Euler's algorithm for finding a GCF is IMO easiest to implement recursively. Here's a rough (i.e. totally unoptimized offthetopofmyhead) recursive implementation:
Spoiler:
There's no such thing as a funny sig.
 LucasBrown
 Posts: 299
 Joined: Thu Apr 15, 2010 2:57 am UTC
 Location: Poway, CA
Re: Useful applications of recursion?
You mean the Euclidean algorithm? That's actually (IMO) more obvious to implement iteratively than recursively. For example, in Python we have
but now that I think about it, the recursive solution is a bit more elegant:
Code: Select all
def gcd(a, b):
while b: a, b = b, a%b
return a
Code: Select all
def gcd(a, b): return gcd(b, a%b) if b else a
 thoughtfully
 Posts: 2253
 Joined: Thu Nov 01, 2007 12:25 am UTC
 Location: Minneapolis, MN
 Contact:
Re: Useful applications of recursion?
I don't know if this qualifies as useful, but I once combined recursion with lazy evaluation to obtain an iterator for the columns of Pascal's Triangle. For instance, f(0) produces 1,1,1,1..., f(1) the Whole Numbers, f(2) the Triangular Numbers, and f(3) Tetrahedral Numbers.
Here's Pascal's Triangle in righttriangle format, just as a reference.
Code: Select all
def pascol(n):
if n == 0:
while True:
yield 1
else:
g = pascol(n1)
a = 0
while True:
a += g.next()
yield a
Here's Pascal's Triangle in righttriangle format, just as a reference.
Code: Select all
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5
Who is online
Users browsing this forum: Jplus and 10 guests