Page 1 of 1

Useful applications of recursion?

Posted: Sat May 30, 2015 6:14 am UTC
by commodorejohn
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?

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 7:04 am UTC
by dalcde
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)

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 7:15 am UTC
by jestingrabbit
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

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 7:23 am UTC
by Flumble
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.

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 7:26 am UTC
by hotaru
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)

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 2:41 pm UTC
by DaveInsurgent
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.

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 2:43 pm UTC
by DaveInsurgent
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?

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 4:02 pm UTC
by EvanED
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.

Re: Useful applications of recursion?

Posted: Sat May 30, 2015 5:22 pm UTC
by Flumble
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

Re: Useful applications of recursion?

Posted: Sun May 31, 2015 2:26 am UTC
by DaveInsurgent
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+

Re: Useful applications of recursion?

Posted: Sun May 31, 2015 6:53 pm UTC
by Derek
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.

Re: Useful applications of recursion?

Posted: Sun May 31, 2015 9:02 pm UTC
by DaveInsurgent
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?

Posted: Sun May 31, 2015 9:27 pm UTC
by hotaru
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.

Re: Useful applications of recursion?

Posted: Sun May 31, 2015 11:03 pm UTC
by notzeb
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, ...

Re: Useful applications of recursion?

Posted: Sun May 31, 2015 11:59 pm UTC
by Rysto
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?

Posted: Mon Jun 01, 2015 1:30 am UTC
by Thesh
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.

Re: Useful applications of recursion?

Posted: Mon Jun 01, 2015 5:15 am UTC
by Derek
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?

Posted: Mon Jun 01, 2015 5:31 am UTC
by Wildcard
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));
      }
   }

Re: Useful applications of recursion?

Posted: Mon Jun 01, 2015 2:57 pm UTC
by LucasBrown
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

Re: Useful applications of recursion?

Posted: Mon Jun 01, 2015 4:29 pm UTC
by thoughtfully
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