Useful applications of recursion?

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

Moderators: phlip, Moderators General, Prelates

commodorejohn
Posts: 962
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Useful applications of recursion?

Postby commodorejohn » Sat May 30, 2015 6:14 am UTC

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?

Postby dalcde » Sat May 30, 2015 7:04 am UTC

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)

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Useful applications of recursion?

Postby jestingrabbit » Sat May 30, 2015 7:15 am UTC

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.

User avatar
Flumble
Yes Man
Posts: 1951
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Useful applications of recursion?

Postby Flumble » Sat May 30, 2015 7:23 am UTC

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.

User avatar
hotaru
Posts: 1025
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Useful applications of recursion?

Postby hotaru » Sat May 30, 2015 7:26 am UTC

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 (1) `mod== 1

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

Re: Useful applications of recursion?

Postby DaveInsurgent » Sat May 30, 2015 2:41 pm UTC

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?

Postby DaveInsurgent » Sat May 30, 2015 2:43 pm UTC

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: 4327
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Useful applications of recursion?

Postby EvanED » Sat May 30, 2015 4:02 pm UTC

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.

User avatar
Flumble
Yes Man
Posts: 1951
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Useful applications of recursion?

Postby Flumble » Sat May 30, 2015 5:22 pm UTC

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? :P

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

Re: Useful applications of recursion?

Postby DaveInsurgent » Sun May 31, 2015 2:26 am UTC

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: 2154
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Useful applications of recursion?

Postby Derek » Sun May 31, 2015 6:53 pm UTC

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?

Postby DaveInsurgent » Sun May 31, 2015 9:02 pm UTC

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

User avatar
hotaru
Posts: 1025
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Useful applications of recursion?

Postby hotaru » Sun May 31, 2015 9:27 pm UTC

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 (1) `mod== 1

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

Re: Useful applications of recursion?

Postby notzeb » Sun May 31, 2015 11:03 pm UTC

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: 1459
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Useful applications of recursion?

Postby Rysto » Sun May 31, 2015 11:59 pm UTC

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.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5519
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Useful applications of recursion?

Postby Thesh » Mon Jun 01, 2015 1:30 am UTC

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.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

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

Re: Useful applications of recursion?

Postby Derek » Mon Jun 01, 2015 5:15 am UTC

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.

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

Re: Useful applications of recursion?

Postby Wildcard » Mon Jun 01, 2015 5:31 am UTC

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.

User avatar
LucasBrown
Posts: 293
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Useful applications of recursion?

Postby LucasBrown » Mon Jun 01, 2015 2:57 pm UTC

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

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

Re: Useful applications of recursion?

Postby thoughtfully » Mon Jun 01, 2015 4:29 pm UTC

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


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests