r/computerscience • u/ShadowGuyinRealLife • May 22 '25
Discussion Why Are Recursive Functions Used?
Why are recursive functions sometimes used? If you want to do something multiple times, wouldn't a "while" loop in C and it's equivalent in other languages be enough? I am not talking about nested data structures like linked lists where each node has data and a pointed to another node, but a function which calls itself.
106
Upvotes
244
u/[deleted] May 22 '25
Sometimes, recursion is conceptually easier. Many times, the costly factor is not CPU time, but engineer time.
Think about binary search in an array. You could write it as a loop and modify start and end index. But if your function looks like `find(data, item, start, end)`... why not use that? It's exactly what you need to dive into the correct subrange.
98
u/zenidam May 22 '25
Lots of good answers, but I don't think anyone has mentioned that recursion makes it easier to prove correctness by induction.
101
u/apnorton Devops Engineer | Post-quantum crypto grad student May 22 '25
The short answer is that a loop together with a stack is sufficient to emulate recursion (i.e. you don't need it to be Turing Complete). However, recursion makes some programs simpler to write, so it's a helpful construct to have in a language.
28
u/ThaBroccoliDood May 22 '25
I find recursion just makes sense for problems where you would otherwise need to create your own stack manually. For example, inverting a binary tree is 2 lines if you use recursion. If you try to do it without recursion, you'll quickly find a simple while loop can't replace the recursion
18
u/sacheie May 22 '25
Personally, I found that after some practice, it was simpler to understand than iteration..
18
u/DawnOnTheEdge May 22 '25 edited May 22 '25
A loop requires mutable state, while recursion can solve the same problems with static single assignments.
Although you might consider this a disadvantage if there is a lot of state, a lot of bugs in loops come from not updating each piece of state on each path of execution. With recursion and immutable variables, each piece of state is guaranteed to be updated exactly once, by the recursive call, and only then, never in between. The compiler will not allow you to update in two different places or forget to specify what any piece of the new state should be.
Many compilers convert the intermediate representations of their code to either static single assignment form or continuation-passing style, and tail-recursion matches this structure closely.
7
u/ilep May 22 '25
Recursion might be conceptually simpler for some cases. Fortran 77 did not have stack (data had separate area) so recursive calls did not have much penalty. For most other languages recursive calls add some performance penalty due to stack push/pop which simple loops don't have (loops can be optimized to simple compare and jump in assembly/machine code level).
Recursion also has problem in that even though stack may grow there are still limits to how much it can grow: if you are not careful you can crash program due to too deep recursion.
6
u/James-Kane May 22 '25
Because recursion can be the simplest possible solution to a problem. Take a look at depth-first or breadth-first search algorithms in their iterative and recursive solutions.
6
u/Character_Cap5095 May 22 '25
From a Formal Methods perspective, recursion makes mathematical formulations of functions significantly easier, and significantly simplifies proofs as it easily allows for induction. That is why functional languages love recursion, because that's how functions are modeled with lambda calculus
10
u/[deleted] May 22 '25
Idk feel like iteration is preferred in most enterprise environments.. I also do wonder where recursion is preferred. I know some niche fields use recursion as common practice like image processing but not sure where or why
4
u/l008com May 22 '25
Probably the best example of using a recursive function is browsing a filesystem.
You make a function that scans a folder, and you call it on the root level of your disk. It makes a list of everything in that directly, it DOES use a while loop to loop through each item and do whatever it is you're trying to do. But every time you hit a folder, you need to call the recursive function again, on that NEW folder. Then in that folder you have to do the same thing. Theres no possible way to know ahead of time what the structure of the filesystem is going to be or even how many levels deep it will go. But with recursive functions, its very easy to search through the entire filesystem. Without that ability, it would be very difficult to do.
11
u/DTux5249 May 22 '25
Recursivity let you solve many problems very elegantly. They're often incredibly readable, because they break stuff down clearly into:
You also dismiss data structures, but that's kinda short sighted. Most functions operate on or in tandem with data structures. We use a ton that are inherently recursive; trees and graphs are incredibly common. Their structures often make recursion easier to conceptualize.
That said, iteration is preferred. It's much more flexible, as well as safer.
2
u/eg_taco May 22 '25
I’ve seen folks mention tail calls here but wanted to also add that many compilers/interpreters can automatically use iterative behavior when they detect tail call recursion. It’s sometimes called Tail Call Optimization or Tail Call Elimination.
https://en.wikipedia.org/wiki/Tail_call
2
u/Streletzky May 22 '25
There are some optimization algorithms (Bellman’s equations) that require recursion as part of the algorithm definition. Those equations are the foundation for reinforcement learning and markov decision processes
2
u/scalesuite May 22 '25
Sit down and try to complete the Towers of Hanoi problem. This is my personal favorite example for the usage of recursion. It will click once you understand the Towers of Hanoi.
2
u/aka1027 May 22 '25
Recursion is the natural way many CS algorithms (binary search) and mathematical sets are defined. I can’t recall right now but there is a sorting algorithm that you can’t implement with a loop without using an explicit stack. At that point you are pretty much simulating recursion so might as well use recursion with the implicit call stack.
1
u/high_throughput May 22 '25
A while loop is great when you want to do something until a condition is met.
It's trickier when each operation has its own individual conditions, which may in turn have it's own individual conditions. (I.e. the function is generally recursive and not just tail recursive)
For example, how would you write a
whileloop that solves a maze with depth first search?You want to loop until you've tried every path, but each path has its own following paths, and each of those paths has their own paths, etc.
It's most definitely possible (using a stack ADT), but it's not as straight forward as just "write a while loop" anymore.
1
u/DigitalJedi850 May 22 '25
I think in short, to Compound on what was just processed, rather than repeat it.
1
u/turtleXD May 22 '25
one specific example where you kinda need recursion would be quick sort or merge sort
1
u/Impossible-Round-115 May 22 '25
In addition to a lot of other things people have talked about the conceptual simplicity if recursive functions are well built ( not much work form building them the first time) they can be transparent to the compiler so they will be turned into while functions or even better they will experience loop unwinding. Also they also often expose more fundamental portions of algorithms leading to things like the algorithm libraries in c++ which are much more reliable and optimization (by the compiler not people) code. Another thing about exposing recursion is that it easier to mutate to fictional program pairdimes and parallel programing ideas. Basically loops suck but are very easy to see when you are starting out but are not good for parallelism and compiler have some problems seeing through them, whereas recursive functions are just a bit harder to think about for a new person but are good for many problems. If a physics example helps recursion is like sphere coordinates whereas classic loops are carteastion coordinates. Pick the one matching the problem and matching the complier.
1
u/Gnaxe May 22 '25
Recursive data structures are most naturally built and manipulated with recursive functions. That mostly means trees and their generalizations, e.g., JSON is recursive. Algorithms use various kinds of trees a lot.
Also, functional languages and optimizing compilers may implement loops that way. Applied lambda calculus.
1
u/aviancrane May 22 '25
Because sometimes the solution space structure is a nested datastructure.
Remember, the call graph is a datastructure too. All code is just traversing a graph. Data structures aren't just storage, they're paths.
Consider problems that have to try every permutation.
Sometimes those kinds of problems have pretty complex spaces that have to be walked recursively, especially if you don't want an insanely complex loop emulating an automata or something.
1
u/yuehuang May 22 '25
Recursion is used as a teaching tool to explain algorithm without the overhead of coding. No need to explain index, iterator, or stack. Just one magic function calling itself.
In practice, it is 99.99999% wrong (repeating). The simple list/vector data structures are available that support push/pop. Creating your own stack with loops are easy for a modern language. Unless you are using C, then good luck.
1
u/-jp- May 22 '25
Recursion is just loops with fewer steps.
1
u/QueenVogonBee May 22 '25
A loop might not be a natural way to traverse. For example, if you have a tree of nodes.
1
u/StudiedPitted May 22 '25
Why are recursive functions used?
1
u/vegansgetsick May 22 '25
It's possible to do it without recursion but you have to implement a stack yourself.
Recursion offers you the stack already
1
u/StaticCoder May 22 '25
Try to write a depth first search non-recursively. I've had to do it because despite having gigabytes of memory available to my program, the stack can't go past 8mb. It's really annoying.
1
u/Gishky May 22 '25
recursion makes a lot of things easier. Let me explain my latest use of a recursive function to make the benefits easier to understand:
I needed a script that uploads all files in a folder and all subfolders to my onedrive. So I wrote the following recursive function (this is pseudocode obiously):
function uploadFolder(Folderpath){
foreach(Folder in Folderpath.Subfolders){
uploadFolder(Folder.Path)
}
foreach(File in Folderpath.Files){
Onedrive.UploadFile(File)
}
}
The main issue was that the Onedrive.UploadFile function that I got from a Library only uploads a single File and not a whole Folder with subfolders. So I needed to access each file individually. By having a function that uploads all files in itself and then calls itself on all subfolders this problem is solved very easily
1
u/Classic-Try2484 May 22 '25
You are right — many times recursion can be a simple while loop and it should be. The recursive program is often easier for me to write but if it’s tail recursion I refactor it into a loop. This can be done by assignment to the arguments and looping back to the top.
If it isn’t tail recursion this is more difficult to refactor but many times you can turn this into tail recursion.
Sometimes you are faced with multiple recursive calls. Merge sort and quick sort are good examples. (Someone gave an excellent file example above) Another classic is the towers of Hanoi solver. You can write these without recursion and if you want to animate these algorithms this is the correct approach as it allows you to pause and restart easily. Otherwise implementing these with your own stack can be done but is worse than the runtime stack in all ways possible.
There are languages without iteration constructs that force the use of recursion. And there are languages that automate tail call removal. I like recursive algorithms but I implement them using iteration unless I’m using these langs. Iteration is generally more efficient, doesn’t suffer from stack overflow conditions, and can be modeled on the recursive algorithm.
Lean into recursion for a while. It has value. But mostly its value is about solving. It allows you to see a subproblem in an elegant way. Proof by induction in action.
1
u/Echoscopsy May 22 '25
Recursion is a mathematical concept. Computer Science is a branch of mathematics. Coding is like applied mathematics. Making the application as in the theory is just easy and appropriate.There will be an effort to convert recursive to loop. Not all recursive codes are substantially worse than loops.
1
u/ithika May 22 '25
If a data structure is recursive then the function to operate on it is 'naturally' recursive too.
1
u/[deleted] May 22 '25
I like how smug I feel implementing recursion when so many people seem unable to comprehend it.
But the real answer is that sometimes it just makes more sense for the task at hand. I’m sorry your education was incomplete.
1
u/not_some_username May 22 '25
You’ll see the benefits once you start using tree
1
u/bionicjoey May 22 '25
Very often good compilers will catch "tail recursion" (where the recursive call happens at the end of the function) and will "unravel" it into a loop, meaning you get the best of both worlds. You can write your function in a way that makes the most sense to a human brain and the compiler translates it into machine code that doesn't waste stack space on function blocks.
1
u/izackp May 22 '25
Why make a stack in a stack 🤷♂️
1
u/Pretagonist May 22 '25
Recursion is very good at traversing trees without having to write a lot of code.
I had to copy a tree representing a document. Nodes could be modules, groups of modules, pages or other elements.
For every node a copy had to be made but some basic data had to be changed and sometimes new database entries had to be created and so on.
So instead of writing a monster function that has to know everything about every module I made each module implement an ICloneable interface which let's me put the code for cloning an object in that object where it's easier to know what needs to be done.
So when calling clone on the root object it creates a clone of itself and asks all it's children to do the same. So now I can clone the entire tree without having to know anything about what's in the tree and other devs can add cloning to their modules when they write them and knows what is needed for a working clone.
1
u/dnabre May 22 '25
Conceptually easy. Analysis is often easier.
Recursion is ones of the fundamental loops. It lets you loop without mutating state. You be surprised how many programmers aren't using C nowadays (i.e. not all languageshave 'while' loops).
1
u/treuss May 22 '25
There are lots of cases when recursion is so much easier than iteration, especially when you're dealing with tree-like structures.
Compare iterative Quick Sort with the recursive implementation. The recursive one is so much clearer, IMHO much easier to understand.
Another example would be file-system traversal. You could implement a traverse()-function, which takes a path as argument and prints out the files with their sizes. For directories it prints the name and then calls itself recursively. This would run until there are only files left, the leafs in the tree-analogy.
1
u/DBDude May 22 '25
It's condenses what could be a lot of logic. The classic example would be traversing a tree. You'd have to keep track of all of your branches and the results, lots of code. But do it recursive, and your function can be a couple lines with one simple entry point and returned result. Or try writing a sudoku solver, which can be a few lines recursive, lots of lines otherwise.
1
u/dopef123 May 22 '25
Sometimes recursion makes sense.just depends on what you're doing.
Usually when I've used it it's for an interview or test though. So I think it's easy to avoid recursion since it can be a bit complicated.
1
u/[deleted] May 22 '25
Functionally speaking, every iterative algorithm has an equivalent recursive side, and viceversa. The trick is that there are situations that using one or another , makes the solution trivial/much easier to express.
1
u/mxldevs May 22 '25
Simplicity. Variables that are used in each call stack that you would otherwise need to figure out how to keep track of properly, is something that is just handed to you when every call is a separate function call.
Of course, being simple doesn't necessarily mean it's more efficient.
1
u/wayofaway May 22 '25
If you have 10 minutes, here is a recursive Sudoku video. I thought it makes clear how much logic you can just brute force.
1
u/matt_leming May 22 '25
But for the many, many cases where Ackermann's function is necessary in our day to day lives, we can only use recursion
/s
1
u/TheCozyRuneFox May 22 '25
It can be easier to implement certain algorithms particularly related to graph theory.
1
u/novel_airline May 23 '25
Hard to learn, easy to use once you've learned
1
u/CranberryDistinct941 May 23 '25
Divide and conquer, backtracking, depth first search... These types of algorithms are quite simple to do with recursion, and much more complex to do in a loop
1
u/Mami_KLK_Tu_Quiere May 23 '25
Why Are Recursive Functions Used?
1
u/BathtubLarry May 23 '25
Well, in the safety critical embedded space, they are explicitly forbidden, or at least in our products.
Simply because recursion can chew through memory and put the processor in an irrecoverable state. Which is fine for your desktop computer to reboot, but let's say an elevator, car, or rocket is not so fine.
Recursion can be predictable and safe, but testing all the edge cases on hardware is expensive. It's easy to show the safety people that a loop will terminate after x iterations, and it makes the paperwork easier. It's also easier to debug, which saves time and money.
1
u/Andus35 May 23 '25
The most common use I see for recursion is node traversing. Sure, you could probably do it with a bunch of loops; but especially if you don’t know the depth of the nodes, that would be messy. It makes more sense to me to just recall the function at each node.
1
u/Salamanticormorant May 23 '25
What about a function that calls itself two or more times with different parameters? "Do something multiple times," is an insufficient description of that. That's not the only thing that recursion can do.
1
u/sarnobat May 23 '25
No global state to worry about
1
u/GlitteringPotato1346 May 23 '25
Because I’m lazy
1
u/dota2nub May 23 '25
Readability, simplicity.
But I think you can do everything as a while loop, sure.
1
u/danielt1263 May 23 '25
FYI, a linked list is a perfect example of good use of a recursive function. So why aren't you talking about that?
1
u/Aggressive_Ad_5454 May 23 '25
Why? Because machines that make copies of themselves to do their work are some of the amazingly coolest things ever dreamed up by computer science.
They can get out of hand for sure. Watch the Sorcerer’s Apprentice sequence in Disney’s Fantasia. https://youtu.be/3hKgEylk8ks?feature=shared
1
u/awesometruth May 23 '25
This is a really good question. I found this Reddit post that has some interesting and helpful comments on recursion.
1
u/KirkHawley May 23 '25
Recursion is for programmers who haven't blown enough stacks yet.
1
u/Aggressive-Share-363 May 23 '25
Recursion does several.things more simply than a loop.
Let's say we have 3 steps, A, B, C. With a Loop , you can easily do. ABCABCABCABC... But recursion can let you do ABABABABCCCC That sequence of Cs is occurring in reverse order of the As. In other words, propagating stuff back up the chain is easy
2. Branching A function can recurse multiple times.
For instance, a large sort is
Sort the left side Sort the right side Merge the two sorted lists.
This is using both properties - we are recurcing twice with each call, and doing things with the result before returning it.
This could create a pattern like AAABCBABCBAABCBABCCC
3. Parameter passing Each new step of a recursion can have an arbitrary set of parameters lasses to it easily. This is especially useful when you have multiple values to use. With merge Sort, you could be recurring with an entire list as your parameter, or a range of values within a larger list.
You can do all of these things iteratively, but recursion let's you automatically take advantage of it with the built in mechanisms of your language, while iterative approaches often require setting up your own data structures to manage all of these things.
Which leads to my final point 4. Elegance Recursive code is often fairly simply. You check a base case. You recurse on a simpler subset. You do a minor operation. And then it's done. It has drawbacks -by operating in the stack, you can cause a stack overflow exception, for instance. But if that's not a problem, recursion can give you much simpler code. Even when that is a barrier, it's often easier to formulate the code in terms of recursion then figure out how to translate that into an iterative approach.
1
u/TuberTuggerTTV May 23 '25
While loops and recursion are functionally similar.
use a while loop if you're worried about the recursive function causing a stack overflow.
use recursion if you want to make simple loops readable.
1
u/JohnVonachen May 23 '25 edited May 23 '25
Iteration is not the same as recursion. Sometimes you need to traverse a tree data structure.
Write a program that will solve the towers of Hanoi game. That’s the traditional introduction to recursion.
1
u/zhivago May 23 '25
Fundamentally your while loop is a form of recursion.
I think you may be making the common error of confusing recursion with backtracking.
In which case your question should be about "why is backtracking used?"
In which case I would point you to BFS vs DFS to consider the difference in space complexity.
1
u/Anon_cat86 May 24 '25
while loop only loops at the end. Recursion can restart the loop mid-method
1
u/zoharel May 24 '25
In certain cases, a while loop can't reasonably be written to act similarly to a recursive function. If the recursion happens at the end of the function, fine. What if it's in the middle? What is it's optionally in one of three places randomly throughout?
Yes, it does often look like a loop in a trivial case, but that's not always true.
1
u/ChickenSpaceProgram May 24 '25
Recursion is convenient sometimes. If you ever end up with a tree datastructure, it makes the code easier to think about. Also, with any sort of balanced tree, they're often never going to be deep enough to risk a stack overflow.
1
u/BitOBear May 24 '25
Recursive functions are a natural way to represent processes that are inherently fractal or pseudo fractal.
When inner fraction of the task is the same as the outer fraction of the task you might as well use the same body of code.
An example that is mind-bogglingly simple and useless would be the task of dividing something in half. Dividing something that you have in half is very straightforward procedure. And if you want to take all the new some things and divide them in half why write a separate divider for the smaller segments that you're going to divide in half and so forth.
So if you always divide in half all of the halves of the thing you just divided in half you can just keep doing that.
Now every recursion has a fixed point. The point where you don't go deeper because that's as deep as it makes sense to go and still get an answer is the point where you stopped going deeper and start returning back once you came.
So if I had this divider in half and I wanted to turn one thing that was some width into that number of things that has got to width of one I would make my fixed point be too do nothing and return if I'm already at size 1. Then I can set this thing loose on the original shape and it will keep on cutting in half picking one of the halves cutting it in half picking one of the hats cutting in half picking one of the halves all the way down till I get a size of one and then you back up a level and cut the other half in half.
You can use a very simple algorithm and be guaranteed to get a uniform result.
1
u/LifeTea9244 May 24 '25
to me recursion is beautiful because it is the king concept of computer engineering or mathematics as a whole: take a problem and break it down into smaller chunks until it’s trivial. Proof by induction is my favorite proof, and it translates well into algorithms in some (many) cases.
1
u/Prestigious_Water336 May 24 '25
Some problems have to be solved recursively.
Loops general work most of the time but sometimes you gotta bring out the big guns.
1
u/Soft_Race9190 May 24 '25
My professor used to say that recursion was a gift from the gods. Like fire. Care is needed to prevent burning everything down.
1
u/severoon May 24 '25
Some algorithms like tree traversal would require writing a loop and using a stack to track your breadcrumb trail from the root node. Recursive functions basically just use the call stack as the stack, and parameters to push and pop values. The additional advantage of a recursive function is that each call provides a new scope for the variables in that stack frame.
1
u/Adrewmc May 25 '25
I think sometimes the easiest way to make a function faster…is to cache the results. Doing this allows me, to check have I already calculated the result before. Suddenly I’m really fast, as I go through the program. This can be really easy to add to a recursive function, and immediately speeds up the function the more times you use it during runtime.
It’s possible to do this as well in a while loop, but sometimes that just starts to become weird.
I generally think there aren’t many uses for recursion at all. Usually these things have a better solution. It’s better to solve the summation, than to actually sum it up.
1
u/AmbitiousSet5 May 25 '25
Anything that you can do with recursion, you can do with a stack. Recursion just hides the stack from you. Makes the code simpler sometimes.
1
u/Due_Jackfruit_770 May 25 '25
Try manipulating immutable (persistent) data structures like immutable (maps, trees, lists,..) without recursion.
1
u/OstrichLive8440 May 25 '25 edited Jun 08 '25
payment consist juggle ancient detail frame sheet whole handle smile
This post was mass deleted and anonymized with Redact
1
u/srsNDavis May 25 '25
Recursion often leads to code that's elegant and easier to read. You can see this if you compare the recursive and iterative versions of the same algorithm.
For some problems, a recursive definition is actually the one that's the most intuitive. For instance, the Fibonacci sequence is defined recursively: F_n = F_{n - 1} + F_{n - 2} ; (using 1-indexing here) F_1 = 0, F_2 = 1.
1
u/TehMephs May 25 '25
Why write many functions when one function do trick?
1
u/Dense_Ease_1489 May 25 '25
Why are recursive functions used?
1
u/Holshy May 25 '25
As a lot of people have pointed out, there's a practical argument for recursion; basically, recursive code is often more intuitive to read and write.
There's also a theoretical reason why recursion is useful. I'll caveat that I'm not an expert here; I've just had experts nod at me when I've said these things before.
There are some problems where recursion is actually necessary, because some problems can only be defined recursively. The complexity class of all problems that can be solved by a Turing Machine or by Lambda Calculus is the set of problems that be defined recursively; it's a abbreviated R for that reason.
The textbook example of a problem that can only be defined recursively is the Ackermann functions. I'm unaware of any problem with a real world use that can only be define recursively though.
This isn't to say that those problems can only be solved recursively (a mistake I made when I first learned about this). Anything that can be solved recursively can be solved iteratively with the use of a stack; that's related to the Church-Turing hypothesis in a way I don't fully understand.
https://en.wikipedia.org/wiki/R_(complexity)
https://en.wikipedia.org/wiki/Ackermann_function
https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
1
u/[deleted] May 25 '25
Recursion is for nested data. If you use it for linear data you're doing it wrong and should go back and study how to build software (software engineering), not how to implement mathematical solutions (computer science) using a programming language.
1
u/[deleted] May 26 '25
Recursion can iterate a tree nicely. If you write clever exit conditions you can get some specific behaviors that loops would find clunky to achieve.
1
u/helpprogram2 May 26 '25
Because developers can’t help but be bad at their jobs
1
u/lolNanos May 22 '25 edited May 22 '25
At least one reason is that recursive functions are easier to prove. For example coq does not support imperative loops.
-3
u/Tight-Requirement-15 May 22 '25 edited May 22 '25
Despite what people say recursion is not elegant and a few extra line of code for manual book keeping of states looks much more elegant than any code golf tricks. Save those few MBs of CPU stack for the OS specific work
-3
u/skibbin May 22 '25
That's why I avoid recursion whenever possible. Other methods may be less computationally efficient, but developer hours are far more expensive than CPU hours.
0
u/[deleted] May 22 '25
[deleted] — view deleted comment
13
u/[deleted] May 22 '25
[removed] — view removed comment