## Useful applications of recursion?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

commodorejohn
Posts: 1199
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 naively-implemented Fibonacci-sequence 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 Fibonacci-sequence 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 multi-gigaherz 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. (Recursive-factorial is another popular one, that's less absurd since it's still O(n), but when you get down to an effective-performance 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 out-of-hand. 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.

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

### Re: Useful applications of recursion?

Recursion is useful when you want to recurse into tree-like structure, eg. if you want to check if there is an element of the tree named "foo", you might have

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 log-length 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
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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 multi-gigaherz 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.

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

### 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 ttwoFibs :: 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.Arrowimport Data.Listimport Data.Numbers.PrimesbitCount 0 = 0bitCount n = uncurry (+) . first bitCount \$ divMod n 2swing 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 ++ pListCrecFactorial n | n < 2 = 1               | True  = (recFactorial \$ div n 2) ^ 2 * swing nfactorial 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 1isPrime n = factorial (n - 1) `mod` n == n - 1`

DaveInsurgent
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 non-recursive solution (even as just a talking point, like, do you know that bottom-up is a thing?) or even the obvious-but-still-stumps-90%-of-candidates, "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.

DaveInsurgent
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?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Useful applications of recursion?

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?
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 inside-out.

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) divide-and-conquer algs like mergesort & quicksort. Edit: oh: recursive-descent parsers.

Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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?

DaveInsurgent
Posts: 207
Joined: Thu May 19, 2011 4:28 pm UTC
Location: Waterloo, Ontario

### Re: Useful applications of recursion?

EvanED wrote:
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?
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 inside-out.

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) divide-and-conquer algs like mergesort & quicksort. Edit: oh: recursive-descent 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 non-recursive 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+

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

### 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.

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.

DaveInsurgent
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.)

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

### 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 1isPrime n = factorial (n - 1) `mod` n == n - 1`

notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

### Re: Useful applications of recursion?

Topological sort on a directed acyclic graph. Also, finding articulation points in a graph.

The incredibly clever linear time find-the-median algorithm.

Finding a winning strategy in a two-player game.

The hashlife algorithm, Fast Fourier Transform, Strassen's matrix multiplication algorithm, ...
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

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

### 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.

Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC

### 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.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

### 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.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Useful applications of recursion?

notzeb wrote:The incredibly clever linear time find-the-median algorithm.
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 one-line perl program. (Okay, so I'm exaggerating.)

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 off-the-top-of-my-head) recursive implementation:
Spoiler:

Code: Select all

`   public static int findGCF(int a, int b) {      int smaller;      int bigger;      if (a < b) {         smaller = a;         bigger = b;      } else {         smaller = b;         bigger = a;      }                  if (smaller == 0) {         return bigger;      } else {         return findGCF(smaller, (bigger % smaller));      }   }`
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

Code: Select all

`def gcd(a, b):    while b: a, b = b, a%b    return a`
but now that I think about it, the recursive solution is a bit more elegant:

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.

Code: Select all

`def pascol(n):   if n == 0:      while True:         yield 1   else:      g = pascol(n-1)      a = 0      while True:         a += g.next()         yield a`

Here's Pascal's Triangle in right-triangle 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`

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery