has there ever been an instance recursion has been actually useful and efficient

[apoyusiken]

its not even reliable bc of the call stack..

[Avocado Diaboli]

Explain your reasoning.

[apoyusiken]

13 minutes ago, Avocado Diaboli said:

Explain your reasoning.

im not a software engineer so i dont know much about actual production. for me its reasonable to use recursion for little scripts but it seems like an horrible idea to use it in actual apps, wouldnt you agree? again, idk there is no real reasoning here im just asking. title is a bit dramatic

 

tldr: i am talking about actual production. 

[Avocado Diaboli]

3 minutes ago, apoyusiken said:

it seems like an horrible idea to use it in actual apps, wouldnt you agree?

Why does it seem like a horrible idea to you?

[apoyusiken]

2 minutes ago, Avocado Diaboli said:

Why does it seem like a horrible idea to you?

because its inefficient, not easy to understand upon reading and not even reliable. isnt there a consensus about this?

[Avocado Diaboli]

4 minutes ago, apoyusiken said:

because its inefficient, not easy to understand upon reading and not even reliable. isnt there a consensus about this?

I don't think it's that inefficient. What makes you think it is?

 

To me, recursion is a tool that's worth using in places where it makes sense to use it, like navigating trees. Any tool can have downsides and there's no magic bullet that will solve all your problems in every instance. That's about as broad a consensus as you're going to find.

[Sauron]

15 minutes ago, apoyusiken said:

because its inefficient, not easy to understand upon reading and not even reliable.

I mean that's just not true... it depends on what you're doing but sometimes recursion is a lot more readable than other methods. Efficiency isn't a problem if you know what you're doing and do tail recursion (besides sometimes you just don't care about stack usage). And I don't see why it wouldn't be reliable...

17 minutes ago, apoyusiken said:

isnt there a consensus about this?

Ever heard of functional programming? There are entire languages designed with recursion in mind and some that don't even allow iteration due to immutability rules.

[Franck]

2 hours ago, apoyusiken said:

bc of the call stack

you can recurse using only 3 level of stack. I would have to think but it might be possible with 2. So Stack is not an issue. You have techniques if you know you will go deep or not.

[Guest]

On 4/1/2025 at 4:46 AM, apoyusiken said:

because its inefficient, not easy to understand upon reading and not even reliable. isnt there a consensus about this?

That's exactly backwards.  An algorithm that is inherently recursive can be implemented with an iterative solution (duality).  But, then YOU have to keep track of the data associated with each iteration.  A recursive implementation lets you minimize the amount of local "context" and rely on the stack to keep track of these associations.

Write a piece of code to implement '?' and '*' wildcards in a pattern matching template.  Try it iteratively.  Then, recursively.

The problem with recursive algorithms is placing bounds on the depth of recursion.  But, problems can be redesigned to impose these limits inherently.

And, an iterative algorithm can suffer from the same resource limits; anything that exceeds the amount of static/dynamic memory allocated to track the iterations causes the algorithm to fail.  A recursive algorithm fails by exhausting the stack or heap.  But, the limits aren't hard-coded into the algorithm's implementation.

 

[wasab]

There are things you can only do with recursion. E.g. depth first search algorithms, backtracking algorithms, and any algorithms that involve decision tree. 

 

I don't personally see it too often in real life applications but I did have to use recursion one time to handle nested routes within react router as well as for transversing nested directory within a file system. 

 

Many recursions can be converted to loops by using a queue or stack to simulate recursion, pushing/popping datas onto it, like what you see in a breadth first search algorithm but depending on the problems you are trying to solve, this can be a serious and annoying pain.

 

The point is, recursion has a place, not because it is most efficient, it rarely is compared to just looping but it is often the only thing feasible. 

[wasab]

On 4/1/2025 at 7:52 AM, Avocado Diaboli said:

I don't think it's that inefficient. What makes you think it is?

Well, it is inefficient in that you have to create extra memory for each function call. Each function call will have its own stack memory and local variables so it can be memory inefficient unless you create some outside global variable to share data between all the successive recursive calls. 

 

Not to mention under the hood, there is probably some overhead at the very low level, depending on the programming language and how they implement function/subroutines, local variables usually need to be saved to stack and restore back onto the cpu registers every time CPU "invokes" aka jumps/returns to/from the starting/ending point of a new subroutine. 

 

On 4/12/2025 at 3:55 AM, serverfarm said:

That's exactly backwards.  An algorithm that is inherently recursive can be implemented with an iterative solution (duality). 

True but this is a real pain in practice unless you abstract the tedious part away. Any iterative solution in which the result of a previous iteration depend on the result of a successive iteration is a huge pain to implement iteratively. This is why recursion exists and is preferred for problems that require this. Thank God that recursion exists. 

[Guest]

32 minutes ago, wasab said:

Well, it is inefficient in that you have to create extra memory for each function call.

It's "inefficient" in that you have to create a whole stack frame for each nesting level.  CPUs typically have instructions that make looping very efficient. And, it is relatively easy for the compiler to predict cache contents in a loop vs. a function invocation.

 

But, efficiency, in the 21st century, is a silly diversion from the more important issue of writing CORRECT and MAINTAINABLE code.  Recursion tends to make algorithms a lot easier to understand (and develop!) because it exposes the layered structure of a problem.

E.g., to reverse the elements in a string, list, etc., it sure seems a lot easier to say:

 

reverse(argument) {

    reverse( tail argument )    // i.e., the rest of the argument starting at the NEXT element

    emit( head argument )    // followed by the first element in THIS argument

}

 

A reader looks at this and thinks:

"If I reverse the rest of the list and then append the START of *this* list instance, it effectively reverses this instance!"

[wasab]

24 minutes ago, serverfarm said:

It's "inefficient" in that you have to create a whole stack frame for each nesting level.  CPUs typically have instructions that make looping very efficient. And, it is relatively easy for the compiler to predict cache contents in a loop vs. a function invocation.

True and this also means it is less memory efficient as a result, you need to store memory onto the stack and then restore back, as well as reclaimed the stack after the subroutine finishes. Each single local variable you pass into its function parameters will need to be duplicated for each successive function call, even if argument is a none primitive and just a reference to an object in the heap, that variable containing the reference itself still consumes memory on that call stack. E.g. in c and c++, a pointer always take up 64 bit or 8 byte memory. It is just less memory efficient.

 

This is on top of whatever variable and data you declare within the function, these all consumes memory. If your recursion function consumes 8 bytes constant memory then 10 recursions deep means 80 bytes total memory on the stack. It is not o(1) constant space but rather o(n) and n is the deepest level of recursions. Compare this with loop, you can obviously see the difference. 

 

24 minutes ago, serverfarm said:

But, efficiency, in the 21st century, is a silly diversion from the more important issue of writing CORRECT and MAINTAINABLE code.  Recursion tends to make algorithms a lot easier to understand (and develop!) because it exposes the layered structure of a problem.

 

Agreed, can't argue with this. I would however also add it saves developers a lot of headaches. A lot easier to code, a lot easier to understand, and a lot better developer experiences for problems that recursions are good for. 

Edited April 16 by wasab
Grammar and spelling.

[Guest]

2 hours ago, wasab said:

I would however also add it saves developers a lot of headaches

On the other hand, for folks who aren't familiar with the technique or THINKING in that vein, it can easily confuse.

 

And, it also requires the platform to support recursion -- to the depth required.  For platforms that have constrained stacks -- or, archaic "BAL" style subroutine invocations, the extra mechanisms that must be added can quickly obfuscate what is happening in the algorithm, itself.

 

The problem with discussions about recursion is that the examples typically offered are trivial to implement iteratively.  See, for example, my "reverse" example.  (also, consider how inefficient "reverse" would be with call-by-value semantics!!)

 

Hence my challenge to implement a "match" algorithm that takes a string template and checks to see if it covers a particular string of characters, supporting the '?' and '*' wildcards.  Iterative solutions will easily trip up the implementor as he has to spend so much effort tracking "where he was" when he tried a particular match strategy.

[wasab]

31 minutes ago, serverfarm said:

On the other hand, for folks who aren't familiar with the technique or THINKING in that vein, it can easily confuse.

Recursion is not a frequent thing you see in the real world, i can see why people find it confusing. I personally get confused by it all the time until i grind enough leetcode problems which many of the solutions actually require recursion in some forms. e.g. find the longest diameter in a binary tree(dfs), compute all the combinations of numbers possible that sum up to a certain target(backtrack), and all kinds of dynamic programming algorithms that involves memorization instead of tabulation.

 

not that you need to do any of these in real life but they are just good problems to ask on technical interviews and competitive programming because they do challenge logical thinking. 

 

31 minutes ago, serverfarm said:

The problem with discussions about recursion is that the examples typically offered are trivial to implement iteratively.  Hence my challenge to implement a "match" algorithm that takes a string template and checks to see if it covers a particular string of characters, supporting the '?' and '*' wildcards.  Iterative solutions will easily trip up the implementor as he has to spend so much effort tracking "where he was" when he tried a particular match strategy.

yeah, this is a famous and popular leetcode problem. gets ask all the time. can be done iteratively but it is just a pain. 

[Guest]

4 hours ago, wasab said:

Recursion is not a frequent thing you see in the real world

I actually use it quite frequently -- especially in desktop/server environments where resources aren't as constrained as in, e.g., embedded systems.

 

E.g., I have a daemon that runs on each of my file servers.  N copies of it are started when the system boots -- N being defined as the number of drives hosted on the server.  Each instance looks at a particular mount point ("starting directory") and fetches a unique identifier previously stored for that directory/volume on an external RDBMS -- creating a unique identifier if one does not yet exist.

 

For each file found in that directory, it fetches a previously computed hash and other associated metadata.  If these don't yet exist, it computes them and makes an entry in the RDBMS creating a unique identifier for this "file" and associating it with the identifier for the directory.  If the hash, etc. already exist, then it compares the computed hash against the stored hash and alerts me of any differences.

 

If the file ("name") is a container (i.e., another directory or an "archive"), it recurses, pointing itself at the new "mount point" (the archive under FUSE).

Eventually, the "deepest" archive is examined and all of it's contents -- along with every other file on the volume -- has been examined and/or verified.

 

Trying to do this iteratively is just a housekeeping nightmare; imagine a directory containing a tarball that contains a ZIP file that contains a VMDK that contains a RAR archive that contains... and each with "other" objects existing alongside!

[wasab]

2 hours ago, serverfarm said:

I actually use it quite frequently -- especially in desktop/server environments where resources aren't as constrained as in, e.g., embedded systems.

 

E.g., I have a daemon that runs on each of my file servers.  N copies of it are started when the system boots -- N being defined as the number of drives hosted on the server.  Each instance looks at a particular mount point ("starting directory") and fetches a unique identifier previously stored for that directory/volume on an external RDBMS -- creating a unique identifier if one does not yet exist.

 

For each file found in that directory, it fetches a previously computed hash and other associated metadata.  If these don't yet exist, it computes them and makes an entry in the RDBMS creating a unique identifier for this "file" and associating it with the identifier for the directory.  If the hash, etc. already exist, then it compares the computed hash against the stored hash and alerts me of any differences.

 

If the file ("name") is a container (i.e., another directory or an "archive"), it recurses, pointing itself at the new "mount point" (the archive under FUSE).

Eventually, the "deepest" archive is examined and all of it's contents -- along with every other file on the volume -- has been examined and/or verified.

 

Trying to do this iteratively is just a housekeeping nightmare; imagine a directory containing a tarball that contains a ZIP file that contains a VMDK that contains a RAR archive that contains... and each with "other" objects existing alongside!

I mean you could probably breath first search this which is iterative but it is definitely less readable and more confusing than a recursive approach. 

 

At the end of the day, all recursions can be converted into loops. A theorem actually proves this. In fact, under the hood, that's how compiler writes assembly code to implement recursions. It is just iteratively pushing and popping stuffs onto the call stack like what you see in breadth first search. You can probably do it too manually if your programming language of choice supports goto statements.

 

When people say recursion is less efficient, it is a yes and no. Less efficient at what? Memory? Well yeah. Time? Maybe and maybe not, depending on the algorithms and implementations but it certainly increase development efficiency by miles for the developers. 

 

I would also like to add that ironically BFS with a stack is typically less memory efficient than a recursive DFS in many of the tree transversals.

 

Don't confuse this with recursions done by the compiler though. Unlike tree transversals where multiple children of the parent node are push onto stack, your everyday loops probably do not require pushing and popping of datas. 

 

 

Edited April 16 by wasab
Misspoke and also grammar and spelling

[Hideki Ryuga]

Recursion is heavily used in functional programming naturally.

 

I expect that one of the next evolutions for modern programming language is to add this functional paradigm.

[Guest]

11 hours ago, wasab said:

I mean you could probably breath first search this which is iterative but it is definitely less readable and more confusing than a recursive approach.

In the application cited, there are two advantages to recursive solutions:  one is ease of comprehension (you treat everything "below" *here* as if here was the top of the hierarchy being examined); the other is you can let each of those new threads (processes) operate in parallel.  So, each of the cores in the box can be "doing work" instead of idling.  This is particularly effective because you can have overlapping I/O operations:  one core (process instance) is talking to the RDBMS server to sort out what *it* needs while another core (process instance) is computing the hash of some file on spindle #1 and another core is working on somethingn on spindle 6 and another is emailing the results of its actions, etc.

 

And, you gain all of these performance enhancements "for free"; your code doesn't have to acknowledge the fact that multiple instances might be active at a given time (ACID in the RDBMS inherently gives you concurrency protection).

[wasab]

1 hour ago, serverfarm said:

In the application cited, there are two advantages to recursive solutions:  one is ease of comprehension (you treat everything "below" *here* as if here was the top of the hierarchy being examined); the other is you can let each of those new threads (processes) operate in parallel.  So, each of the cores in the box can be "doing work" instead of idling.  This is particularly effective because you can have overlapping I/O operations:  one core (process instance) is talking to the RDBMS server to sort out what *it* needs while another core (process instance) is computing the hash of some file on spindle #1 and another core is working on somethingn on spindle 6 and another is emailing the results of its actions, etc.

 

And, you gain all of these performance enhancements "for free"; your code doesn't have to acknowledge the fact that multiple instances might be active at a given time (ACID in the RDBMS inherently gives you concurrency protection).

Well, it is not exactly free. Your code actually uses more hardware resources as trade off. New threads means using more cores and likely more rams too but it is kinda semantic at this point. If you have extra hardware resources disposable, ideally you would want to write software in a manner that utilize these extra resources when require right? 

 

Although if you have I/O heavy operations like talking to database, the most ideal way to go about doing it would be asynchronous operations. It will speed everything up and maximize efficiency without relying on extra computational resources such as children threads or children processes(also important to differentiate the two, process is a lot more hardware resource heavy than thread).

 

Although even async operations are not completely free. There is always low level overhead to implement asynchronous execution such as the use of an event loop and task queues. It is still a lot more efficient than threads in which operating system kernel usually has to do extra book keeping for(assuming kernel thread), cost huge overhead, and easily have large amount of idle time in which there is no work to be done.

 

Speaking of event loop, know about programming language rust? I have been learning it the past couple months. It supports async operations but it lacks a runtime for it out of the box. You actually have to import a library called tokio that implements asynchronous runtime. What that library does under the hood is actually running a giant forever while loop in which it constantly polls futures to see if they have been resolved or not. It is very fascinating. 

 

 

[apoyusiken]

56 minutes ago, wasab said:

the most ideal way to go about doing it would be asynchronous operations.

famous last words (out of context)

[wasab]

11 minutes ago, apoyusiken said:

famous last words (out of context)

I don't see how this is out of context, well probably out of tangent since I was no longer talking about recursion but async/await is just better than threads for handling I/O blocking tasks by miles.

 

Threads have context switches, extra memory for keeping track of these context states and on and on. Lots of overhead. People shouldn't just look at threads and parallel processing as if they are free performance. If anything, they can ironically make performance worse, especially if your softwares have no work that can be parallelize. 

[Guest]

4 hours ago, wasab said:

Well, it is not exactly free.

It is free to the developer.  He doesn't have to take extraordinary measures to take advantage of all that memory and cores just sitting there, idle, while he is waiting for the disk to deliver more data or the remote server to process his query.

Resources are cheap.  The cost of a developer's time isn't.  The cost of getting the code RIGHT is even more dear!

4 hours ago, wasab said:

Your code actually uses more hardware resources as trade off.

Yes.  Resources that are sitting there, idle.  Your goal should always be to use all of the resources available to you WITHOUT increasing the complexity of your solution to a point where its correctness becomes suspect.

4 hours ago, wasab said:

the most ideal way to go about doing it would be asynchronous operations.

No.  Developers are notoriously bad at handling asynchronous designs.  They are open to hazzards/races/dropped events, etc.  People have a tough time dealing with EXPLICIT coordinated access to a single resource let alone one where those actions can be skewed in time.

 

What do you do when the target of an asynchronous service request fails/faults?  Can you unroll all of the other actiions that you have taken on the assumption that it WOULD complete?  Successfully?  Folks still write code assuming malloc() will NOT fail to produce the requested memory...

 

(saying that as the designer of a distributed multiprocessor that relies exclusively on RMI in its design).

[wasab]

1 hour ago, serverfarm said:

It is free to the developer.  He doesn't have to take extraordinary measures to take advantage of all that memory and cores just sitting there, idle, while he is waiting for the disk to deliver more data or the remote server to process his query.

No, a thread that is blocked by an I/O is in fact a thread that is IDLE. It is an inefficient use of resources. In I/O bound operations, there is no work to be done on the CPU. If you are reading and writing to a file, for example, your disk controller does the work, not your CPU. If you are making network requests to a server, your CPU does not do the work; rather, the server machines do. In all of these cases, there is no point for your CPU to be idle and doing nothing while waiting for results from these I/O blocking tasks. This also means there is no point for your application and in turn its thread to be idle and blocked while waiting for results from these I/O requests.  A new thread that is blocked by I/O does nothing while blocked. It will result in less than 1% thread utilization a lot of the time, which is a waste. Async is just better. Only one thread is there, so better resource usage, and it is also non-blocking. 

 

Your cores are also not idle. Your operating systems are juggling countless processes, and many of these processes may also have countless threads. These cores are by no means idle. The operating system kernel is itself a giant multitasking piece of software, and context switches and interrupts happen constantly. There just isn't a point in overloading the operating system with more threads and processes when you don't need to. These all have overheads and are quite expensive in terms of system resources and performance hits. 

 

1 hour ago, serverfarm said:

Yes.  Resources that are sitting there, idle.  Your goal should always be to use all of the resources available to you WITHOUT increasing the complexity of your solution to a point where its correctness becomes suspect.

yes, but only when you need to, as explained above. 

 

 

1 hour ago, serverfarm said:

No.  Developers are notoriously bad at handling asynchronous designs.  They are open to hazzards/races/dropped events, etc.  People have a tough time dealing with EXPLICIT coordinated access to a single resource let alone one where those actions can be skewed in time.

Hard disagree with this. Asynchronous has way fewer headaches when it comes to race conditions, and it does not suffer from things like deadlocks and data corruption outside of race. There is a learning curve at the beginning for sure but getting multithreading right is on a whole new level of difficulty, so much so, developers often just spin up child processes rather than threads to get rid of many of the headaches. 

 

Edit: actually async can have deadlocks but these are very rare. you probably need to write code deliberately to cause this to happen. 

 

1 hour ago, serverfarm said:

What do you do when the target of an asynchronous service request fails/faults?  Can you unroll all of the other actiions that you have taken on the assumption that it WOULD complete?  Successfully?  Folks still write code assuming malloc() will NOT fail to produce the requested memory...

Well, you write error-handling code. In JavaScript, the most well-known async event-driven programming language out there, this is when you do try/catch blocks or the .catch chain for promises. It is very trivial to handle. You don't need to roll back either, since the callbacks literally won't execute unless the async operation succeeds. Threads are just more complicated. 

 

 

[apoyusiken]

12 hours ago, wasab said:

I don't see how this is out of context, well probably out of tangent since I was no longer talking about recursion but async/await is just better than threads for handling I/O blocking tasks by miles.

 

Threads have context switches, extra memory for keeping track of these context states and on and on. Lots of overhead. People shouldn't just look at threads and parallel processing as if they are free performance. If anything, they can ironically make performance worse, especially if your softwares have no work that can be parallelize. 

i meant to make a joke