Poll

How often have you come across recursion?

What's recursion?
5 (3.8%)
Never seen a practical need for it
10 (7.7%)
Seen and used it in the classroom, but very rarely in practice
52 (40%)
I implement a new practical solution with recursion about once a year
47 (36.2%)
Not a month goes by without me finding a new practical way to use recursion
16 (12.3%)

Total Members Voted: 128

Author Topic: Recursion - do you use it in the real world?  (Read 41661 times)

0 Members and 1 Guest are viewing this topic.

Offline HowardlongTopic starter

  • Super Contributor
  • ***
  • Posts: 5315
  • Country: gb
Recursion - do you use it in the real world?
« on: September 04, 2017, 04:58:16 pm »
While debugging some customer code in production last week that kept crashing, I came across a recursive function. While it wasn't the recursiveness in itself that caused the problem on its own, it exacerbated the problem (memory allocated but not released).

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons. Had the programmer remembered to release all his initialised variables as they dropped out of scope I might have given him more credence. Those initialised heap variables were arrays of strings that never changed  :palm: so should've been constants anyway, and never used either heap or stack. (The heap grew to... wait for it... 50GB before the process broke.)

I think that in over 30 years I can count on the digits of one hand the number of times I've come across recursion used outside the classroom, and this was one of them. Most of those times have been when looking at the C runtime library, such as qsort.

 

Offline boffin

  • Supporter
  • ****
  • Posts: 1027
  • Country: ca
Re: Recursion - do you use it in the real world?
« Reply #1 on: September 04, 2017, 05:02:04 pm »
I use it quite often, check out this thread.  Recursion - do you use it in the real world?
(sorry, couldn't resist)

Offline stmdude

  • Frequent Contributor
  • **
  • Posts: 479
  • Country: se
Re: Recursion - do you use it in the real world?
« Reply #2 on: September 04, 2017, 05:03:35 pm »
I use recursion quite often actually. Usually when parsing fileformats that either have chunked sections, or simply formats such as XML.

However, this is on PCs, which tons of VM-space and RAM, so I just make sure I keep what I need on the stack, and I should be good.

However, I would never do recursion on an embedded system. It kind of goes against the whole "don't dynamically allocate memory" and "the system should behave the same the first time it's run as when it has been running for 100 days straight" rules.
 

Offline legacy

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: Recursion - do you use it in the real world?
« Reply #3 on: September 04, 2017, 05:12:53 pm »
It depends on the purpose! Algorithms in AI use recursion, e.g. if you have to implement A* or A*++ you have to deal with recursion (and backtracking) :-//
 

Offline bd139

  • Super Contributor
  • ***
  • Posts: 23018
  • Country: gb
Re: Recursion - do you use it in the real world?
« Reply #4 on: September 04, 2017, 05:20:04 pm »
I only use it if I can benefit from tail recursion (64-bit .net CLR and Common Lisp!). Read The Structure and Interpretation of Computer Programs (SICP) for why: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_start but fundamentally tail recursion is readable but executes in one stack frame.

Warning: book messes with your head.

Oh use cases I have used: compilers, parsers, optimisers, various algorithms etc

The main reason we don't seem to see it often is that everything in C languages punishes you by kicking you in the nuts (stack overflows, heap usage etc).

50Gb is smaller than some of the working sets I've seen using recursive code. We've got a few 512Gb nodes that run a matching engine that use 300Gb of RAM on a bad day. You don't want to have to minidump that fucker though. Even with several TiB of enterprise SSD it takes a day.
« Last Edit: September 04, 2017, 05:26:21 pm by bd139 »
 

Offline legacy

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: Recursion - do you use it in the real world?
« Reply #5 on: September 04, 2017, 05:54:47 pm »
well trees need recursion, thus a shell on a filesystem need recursion, as well as some tool which need to operate on filesystem, but also compilers need recursion when they have to deal with AST.

A lot of algorithms in motion planning need recursion!
 

Online rstofer

  • Super Contributor
  • ***
  • Posts: 9886
  • Country: us
Re: Recursion - do you use it in the real world?
« Reply #6 on: September 04, 2017, 06:00:14 pm »
One of the largest examples I have seen is the Pascal Compiler by Niklaus Wirth.  Recursive descent is an elegant way to structure a compiler.  We can go straight from the syntax graph to code!  Algol might have done the same thing but I haven't looked at the compiler code.

A more simple example might be evaluating an expression.  It is common to define an expression in terms of expressions and operators.

The trivial example is using recursion to compute factorials.
 

Offline Bruce Abbott

  • Frequent Contributor
  • **
  • Posts: 627
  • Country: nz
    • Bruce Abbott's R/C Models and Electronics
Re: Recursion - do you use it in the real world?
« Reply #7 on: September 04, 2017, 06:44:05 pm »
Microchip MPLAB XC8 C Compiler (Free Mode) V1.42
Build date: Apr 12 2017
Part Support Version: 1.42
Copyright (C) 2017 Microchip Technology Inc.
License type: Node Configuration

Warning [1273] ; . Omniscient Code Generation not available in Free mode
Error   [1089] C:\code\PIC\test\16F630 blinky.c; 17. recursive function call to "_foo"
(908) exit status = 1
 

Offline sasa

  • Regular Contributor
  • *
  • !
  • Posts: 168
  • Country: 00
  • Hobbyist in electronic
Re: Recursion - do you use it in the real world?
« Reply #8 on: September 04, 2017, 06:56:40 pm »
Microchip MPLAB XC8 C Compiler (Free Mode) V1.42
...

IIRC, only 13 sub calls are allowed in most of small PICs, thus it is anyway pointless to do any recursion here.
The 30+ years professional desktop software designer and software engineer
 

Offline sasa

  • Regular Contributor
  • *
  • !
  • Posts: 168
  • Country: 00
  • Hobbyist in electronic
Re: Recursion - do you use it in the real world?
« Reply #9 on: September 04, 2017, 07:23:22 pm »
I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons.
...

There is several problems here...

1. Some problems can be solved without recursion, but usually is used recursion. One of it is mentioned searching a file in directory tree I have made and use my own class decades ago without recursion. Second one I can remember is Huffman tree, which also can be searched without recursion. And original QSort  have  O(N*N) only in worst case scenarios, however, all that scenarios can be easily bypassed in algorithm... Similar with A* and chosen method searching the shortest path...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.
« Last Edit: September 04, 2017, 07:25:53 pm by sasa »
The 30+ years professional desktop software designer and software engineer
 

Offline fourtytwo42

  • Super Contributor
  • ***
  • Posts: 1183
  • Country: gb
  • Interested in all things green/ECO NOT political
Re: Recursion - do you use it in the real world?
« Reply #10 on: September 04, 2017, 07:25:04 pm »
In my experience heavily used in traffic "classification" algorithms in data communications and decryption :)
Just by way of a partial explanation you dont know the extent of the problem nor the number of branches so unless you have infinite memory recursion is a sensible way to handle it.
« Last Edit: September 04, 2017, 07:27:38 pm by fourtytwo42 »
 

Offline SimonR

  • Regular Contributor
  • *
  • Posts: 122
  • Country: gb
Re: Recursion - do you use it in the real world?
« Reply #11 on: September 04, 2017, 07:32:17 pm »
I'm with stmdude on this

I use recursion for parsing trees, mostly XML but often my own.
But would never use it in a C based embedded project.
All my recursive projects are PC based in C# which should catch any problems which have never happened yet.
 

Offline Cerebus

  • Super Contributor
  • ***
  • Posts: 10576
  • Country: gb
Re: Recursion - do you use it in the real world?
« Reply #12 on: September 04, 2017, 07:53:12 pm »
The time you suddenly realise how often you use recursion is when you use some dumb programming language that doesn't support recursion, like older variants of FORTRAN.

Remember too, that recursion is not always obvious and in your face, such as tail recursion or tree walks, but often lurks a layer or two away in mutual recursion in some very everyday programming.
Anybody got a syringe I can use to squeeze the magic smoke back into this?
 

Offline HowardlongTopic starter

  • Super Contributor
  • ***
  • Posts: 5315
  • Country: gb
Re: Recursion - do you use it in the real world?
« Reply #13 on: September 04, 2017, 08:09:38 pm »
50Gb is smaller than some of the working sets I've seen using recursive code. We've got a few 512Gb nodes that run a matching engine that use 300Gb of RAM on a bad day. You don't want to have to minidump that fucker though. Even with several TiB of enterprise SSD it takes a day.

Funnily enough, this isn't a million miles away from the functionality I was debugging. There's another bit of the system that deals with this, dev guys keep telling me to throw more RAM at the problem, and I assure them that they're welcome to it, once they can tell me how much, how they derived the figure, and why they have an algorithm that needs so much memory. Sometimes, occasionally, it's justified, matching engines are just such an example. Most of the time in my experience it's programmers not being concerned enough about non-functionals such as performance, how much that RAM will cost across multiple environments, and whether we will need to throw even more tin at the problem, and the costs of that.
 
The following users thanked this post: nugglix

Offline bd139

  • Super Contributor
  • ***
  • Posts: 23018
  • Country: gb
Re: Recursion - do you use it in the real world?
« Reply #14 on: September 04, 2017, 08:57:11 pm »
Agree entirely. In this case it was definitely justified. Three of us pulled two weeks of lates hammering at visual studio to move it off an IBM z9 EC that had the consultant vultures waiting to swoop on a renewal and hardware refresh. Efficiency was a low priority. Make the big blue consultants bugger off was priority. We had a few mid-range HP DL560 chassis lying around idling on load standby so we just used them. The dataset was crudely piped entirely into RAM daily and processed there with LINQ because we didn't understand the model very well on the z9.

Now we understand it, it's all being carefully rearchitected with SQS/EC2/ElastiCache Redis on AWS now powered by glorious C++11 via clang/LLVM on CentOS. Finally something that isn't a corn filled turd to play with :D
« Last Edit: September 04, 2017, 09:00:04 pm by bd139 »
 

Offline janoc

  • Super Contributor
  • ***
  • Posts: 3781
  • Country: de
Re: Recursion - do you use it in the real world?
« Reply #15 on: September 04, 2017, 09:47:37 pm »
There is several problems here...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Actually it goes both ways - any iteration can be expressed as a (tail) recursion and any recursion can be expressed using an iteration + counter or stack. There is actually a theorem on this (paper from 1966):

https://academic.oup.com/comjnl/article-pdf/9/1/45/997564/9-1-45.pdf

Now whether to use one or the other depends on the problem and things like constraints of the technology you are using - if the compiler doesn't do tail call optimization, then recursion could be an expensive option vs iteration. On the other hand,  algorithms on some more complex data structures, such as the already mentioned trees or graphs are much more naturally expressed using recursion. They can be implemented iteratively but the code will be a pain to read and debug ...

Also it depends a lot on the programming language - in some high level languages, especially functional ones, recursion is the thing to use and loops are frowned upon (or even impossible because the language doesn't have the construct - tail recursion can do all that a loop can!)

People doing low level embedded programming won't see it that much, because recursive algorithms in C++ or C on an MCU are pain due to the small stack and lack of tail call optimization. But there are ports of e.g. Scheme to small MCUs if someone wants to try that.
« Last Edit: September 04, 2017, 09:49:58 pm by janoc »
 

Offline MrTurk

  • Newbie
  • Posts: 8
Re: Recursion - do you use it in the real world?
« Reply #16 on: September 04, 2017, 09:48:52 pm »
 In DSP, IIR filter design is a recursive computation of inpulse responses but nobody uses IIR filters IMO

Nexus 5 cihaz?mdan Tapatalk kullan?larak gönderildi

 

Online nctnico

  • Super Contributor
  • ***
  • Posts: 26755
  • Country: nl
    • NCT Developments
Re: Recursion - do you use it in the real world?
« Reply #17 on: September 04, 2017, 10:05:29 pm »
I'm using IIR filters exclusively  8) But no real-time calculation of coefficients.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2803
  • Country: nz
Re: Recursion - do you use it in the real world?
« Reply #18 on: September 04, 2017, 10:42:26 pm »
I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons.
...

There is several problems here...

1. Some problems can be solved without recursion, but usually is used recursion. One of it is mentioned searching a file in directory tree I have made and use my own class decades ago without recursion. Second one I can remember is Huffman tree, which also can be searched without recursion. And original QSort  have  O(N*N) only in worst case scenarios, however, all that scenarios can be easily bypassed in algorithm... Similar with A* and chosen method searching the shortest path...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Completely agree - recursion is usually suited only to quick hacks, and in cases when resource usage cannot be a problem.

The classic text-book example used to be a 'factorial' function:

Code: [Select]

int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Offline brucehoult

  • Super Contributor
  • ***
  • Posts: 3998
  • Country: nz
Re: Recursion - do you use it in the real world?
« Reply #19 on: September 05, 2017, 06:09:01 am »
Code: [Select]

int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....

Hmmmm. Let me try that...

Code: [Select]
$ gcc recfact.cpp -c -Os -o recfact.o
$ objdump -d recfact.o

recfact.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <_Z9factoriali>:
   0: 4785                li a5,1
   2: 873e                mv a4,a5

0000000000000004 <.L3>:
   4: 00e50663          beq a0,a4,10 <.L1>
   8: 02a787bb          mulw a5,a5,a0
   c: 357d                addiw a0,a0,-1
   e: bfdd                j 4 <.L3>

0000000000000010 <.L1>:
  10: 853e                mv a0,a5
  12: 8082                ret

Yeah, nah .. no segfault there, your stack will be fine.

*Arithmetic* overflow, however ,,, for sure.
 

Offline sasa

  • Regular Contributor
  • *
  • !
  • Posts: 168
  • Country: 00
  • Hobbyist in electronic
Re: Recursion - do you use it in the real world?
« Reply #20 on: September 05, 2017, 06:18:12 am »
I have seen quite a few catastrophically losing code in my professional career, no matter is it free or commercial software.

Programming language can learn (conditionally) anyone in a weekend or few, but the difference between pure and good programmer is to have algorithms in his little finger using appropriate for the task, have ability to make a suitable corrections in it if needed, perform appropriate optimization and finally, as a result, it will have optimal solution for the task.

Take for example mentioned sorting. Everybody know that original QSort is one of the fastest in-place sorting algorithms (except in worst case scenarios), however his recursive nature may be extremely dangerous. If there is maximally 100's of data to sort, the most optimal solution may be to use Shell or even Insertion...

Proper decision depends on precisely defined requirements, according to complete software design. Often is much more beneficial if CEO have no grasp about programming, instead to know a bit, combining with a "God complex", including as well working environment with junior software engineers. That is a nightmare for any skilled and experience programmer.
« Last Edit: September 05, 2017, 06:20:38 am by sasa »
The 30+ years professional desktop software designer and software engineer
 

Offline brucehoult

  • Super Contributor
  • ***
  • Posts: 3998
  • Country: nz
Re: Recursion - do you use it in the real world?
« Reply #21 on: September 05, 2017, 06:32:59 am »
2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Completely agree - recursion is usually suited only to quick hacks, and in cases when resource usage cannot be a problem.

I agree that recursion is clearer.

Probably any complex loop can be rewritten more clearly using recursion, especially if there are multiple continues or breaks or multiple state variables to update when you loop. Each "continue" (or goto the start/end) becomes a recursive call, with the updated state variables as the arguments. And each recursive call will be tail-recursive, so with a decent compiler will cost absolutely nothing compared to writing it as a loop.

Even many things that don't *look* tail recursive can be transformed into tail recursive by a modern compiler. Your  factorial code, for example.

Transforming a naturally recursive function into iteration with an explicit stack saves virtually nothing. You might manage to use an 8 or 16 bit enum as the state to return to in your switch in your loop, instead of a 32 bit or 64 bit return PC, but that's *it*. Ok, maybe a frame pointer too if your compiler sucks or your ABI requires it (i.e. sucks). All the rest of the state saved will be identical (and identical size) in either case. The only excuse is if you're using a processor with a very limited size hardware stack.

Assuming you're processing some actual data structure in memory, and not just some abstract math function, the size required for the stack is usually no more than the number of items in your data structure, and usually it's the log of the size of your data structure. e.g. if you've got a million items of data then your recursion is probably on the order of 20 levels deep if you avoid pathological cases. For a billion items of data, 30 levels deep. Even with a fair bit of state to save on each call you're probably talking something like a KB or two of stack.
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 21606
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
Re: Recursion - do you use it in the real world?
« Reply #22 on: September 05, 2017, 06:39:34 am »
2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Correct.  Syntactic recursion in code is syntactic sugar, another (usually inefficient) way to implement it.  One can implement the same thing with a software stack (or queue, if you're perverted like that).

Or a loop with fixed state variables, for special cases (that really shouldn't ever be recursive).  The trivial-but-please-don't-ever-do-this examples: the factorial and Fibonacci functions, aren't even deserving of O(N) loops!

I voted "new practical solution with recursion about once a year", because although it's a lie, that's mainly because I don't do much programming.

Recursion is a useful and powerful tool, that like all tools, must be used responsibly.  If you ever have a question about your program: quantify it.  Add flags or timers, to record the execution time of a function.  Add bounds checking and limits, especially for recursive functions that can potentially use unlimited stack space!  And check your inputs and outputs.  At least fuzz the inputs.  It's utterly practical, these days, to test the entire 32-bit input space of a two-parameter, 16-bit function (only 4.some billion possible inputs).  Why deprive yourself of such cheap security?

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline sasa

  • Regular Contributor
  • *
  • !
  • Posts: 168
  • Country: 00
  • Hobbyist in electronic
Re: Recursion - do you use it in the real world?
« Reply #23 on: September 05, 2017, 06:46:28 am »
I would suggest OP to add following in a pool:

"Use recursion only when necessary or appropriate."

That is the most correct answer.
The 30+ years professional desktop software designer and software engineer
 

Offline BillyD

  • Regular Contributor
  • *
  • Posts: 218
  • Country: ie
Re: Recursion - do you use it in the real world?
« Reply #24 on: September 05, 2017, 06:54:41 am »

Well in order to define recursion, one must first define recursion.


I agree with the view that you should use it if you must, and not if you can. In terms of clarity and maintainability it can sometimes be the best approach, but if resources or scalability are an issue it's usually a non runner.


 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf