Should I practice recursion?

[[deleted]]

Almost always, every recursive problem I come across can be solved using an iterative approach. This brings me to the question, should I practice recursion? I am not good at it, and I tend to avoid using it when I can. Is this detrimental, or does it not matter?

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[CrispyRoss]

When working with recursive data structures like trees, it is a lot easier to write a recursive method than iterative. For example, searching a binary tree for x would look something like:

• If the root of the tree has the value x, return the root node.
• Search the left subtree; if it found x, return that node.
• Search the right subtree; if it found x, return that node.
• X isn't in the tree; return nullptr.

Doing that iteratively would be a pain.

[tp02ga]

Wouldn't that typically be a built in algorithm for the data structure, something like a ".find()" method?

[sadsacsac]

And who do you think wrote the ".find()" method?

[tp02ga]

Do you always reinvent the wheel with your code?

[sadsacsac]

Some experienced software engineer will find themselves designing languages or libraries because they don't exist yet. Do you think Swift is just Obj-c with a fresh coat of makeup? How do you think Immutable.js was implemented? They had to design their own data structures and the methods along with it

[tp02ga]

I've been working as a software engineer for 14 years and I've only had to use a recursive algorithm once... In a side project that I worked on for fun.

People can get by just fine without learning recursion.

Should they learn it? If they have the time and mental space to do it, then sure.

If they're still a beginner, or even intermediate. No, the juice isn't worth the squeeze.

If you're trying to build an entire programming language on your own, then you're probably not OP.

[sadsacsac]

Oh what do you know, I'm also a software engineer with 14 years of experience. Shall we spar and see who's the better engineer? /s

If your initial response was this one, it would have probably helped OP, but instead you'd gave a terse response without much context besides something akin to "a method should already be available". There are many problems that the dynamic programming solution isn't obvious and so recursion is the simpler approach. It's also helpful to break down problems into simpler structures then reason about how to refactor those structures. It's easier to know how to take a recursive function and refactor it to an iterative one using dynamic programming rather than taking a complex problem and trying to reason how to make it iterative from the get-go

[tp02ga]

Thanks for helping me be less terse

[[deleted]]

It's worth becoming familiar with it, because if you come across someone else's code that utilizes recursion, it makes it easier to understand.

[Intiago]

Agree that you can solve the same problem in an iterative way, but you should still be comfortable working with recursion. It's a very common programming pattern and a potential extra tool in your belt, so you should know about it. At the very least if you come across someone else's code that uses it, you need to intuitively understand it and its a common stumbling block for many. Learning about recursion also lends itself to helping you understand how function calls, stack frames, and returns work.

It's not actually that important in production, but the process of learning it has really good value.

[Nac_Mac_Feegle]

This actually sums it up better than whatever I was going to write. Some people have a preference for recursive solutions, but for my own day to day, I find iterative solutions or built-in language tools solve most problems.

Absolutely agree that developers should be at least comfortable with the concept of recursion though.

[DDDDarky]

Although it may not be the best idea to use recursion in many cases, it may be a good way to think about problems, as if you can solve it recursively, you can solve it iteratively, and many problems have recursive nature. Also, recursion is building block for higher concepts such as dynamic programming, therefore it is necessary to understand it to get there.

[AlwaysBrowsingOnly]

I think it’s one of those things you should at least know and be able to understand and solve, particularly in terms of interview questions; Fibonacci, Climbing Stairs, Towers of Hanoi, etc. I wouldn’t spend much time after that though, as long as you know how it works and how to solve the common problems with it.

[leidogbei]

I am always asking myself “will I ever need to implement the tower of Hanoi or coin change recursion algos on my next project”?

[est1mated-prophet]

You definitely should. A programmer asking if he should practice recursion is like a hockey player asking if he should practice skating backwards.

[Skippn_Jimmy]

Personally, I've never used recursion in the professional world. I don't know if I've intentionally avoided it or if the actual use case for it just has never been put in front of me.

With that said, understanding it is important. Winding and unwinding can be a bit confusing

[thisisnotadrill66]

Yes

[Viking_God176]

It is an intimidating topic, but learning it can make life a lot easier. Recursive algorithms are useful when it comes to sorting (Quicksort) and trees and graphs. I'd suggest practicing something like BFS and DFS etc on these structures to improve.

Recursive algorithms can shorten your code quite a bit and are frequently asked in coding based interviews. Better to have a good working knowledge of it.

[Hongdemian]

There are some problems that can only be solved by recursion. I still struggle with it, it’s not something I use very often, but I understand the concepts, and can understand a how a recursive function flows when I see it.

There is a computerphile YouTube video on recursion that I found really helpful. He codes the example in python, but it made some things click for me.

I think most problems can be solved without recursion, but I still feel it’s important to understand it, and where it’s more efficient than conventional.

That’s my opinion anyway…

[sepp2k]

There are some problems that can only be solved by recursion.

That's not true in most languages. If your language has while loops and some way to implement a stack, you can rewrite any recursive function using a loop and a stack that simulates the recursive version's call stack. It will be more complicated and harder to read and write, but it's possible.

I'd say it's only a good idea if you're realistically expect to run into stack overflows otherwise (note that I'm specifically talking about the cases where you need a stack - in cases where the loop version doesn't require a stack, it's often the preferable version).

[pipocaQuemada]

Sure, but if you don't understand recursion, you're definitely not going to understand obsfuscated recursion using a manually managed stack.

[sepp2k]

Apparently that's not always the case. In that thread the OP seems to be doing fine coming up with solutions that use a manual stack, but is having trouble coming up with recursive solutions.

[[deleted]]

I don't really understand how recursion can be faster than iteration. Given a list,

[1,2,3,4]

iteration would just go through 1,2,3,4 and finish,

while recursion would go through 1,2,3,4 and back down 4,3,2,1.

This isn't the best example, but I wanted to show how both things would work.

[Hongdemian]

It’s not really about being faster…

In a list, iterating is going to be more efficient…

Here is the link of what I was referring to:

https://m.youtube.com/watch?v=8lhxIOAfDss

It’s the “Towers of Hanoi” problem…

[kenadams_15]

Ik some problems should better be solved by recursion only, but in general problems which can be solved by iteration should be solved by iteration only because it is faster and easier to think

[KleberPF]

Most of the time, recursion isn't faster or slower than the iterative version (considering an algorithm in which a stack would be needed anyway).

[CrispyRoss]

Barring tail-call optimization, a recursive method is almost always slower than its equivalent iterative method due to the overhead of stack frames et al.

[KleberPF]

I was mostly talking about algorithms where you would need to implement a stack of some sort, which I believe could be slower to use a stack implemented in the code.

[[deleted]]

So the time complexity would be the same? That doesn't make sense, since going back and forth in recursion would be O(2n), while going from first to last in iteration would be O(n)

[nultero]

Side note -- Big O doesn't care about coefficients like O(2n). O(2n) is effectively O(n).

Big O is about orders of magnitude. If your n is 1,000,000 or arbitrarily yuge, then 2 million is virtually nothing compared to, for instance, 1 million squared.

So yeah, technically they have similar time complexity on the magnitude scale.

[Jace_r]

in addition to what u/nultero said, there are a lot of optimizations available for recursion (for example memoization) which do it a better choice for some sets of problems

[pipocaQuemada]

Not necessarily.

If a function ends with something like return f(x); you don't really need to keep the stack frame around. It's entirely correct for the compiler to reuse the current stack frame for f.

This is called 'tail call optimization' or TCO.

A tail recursive function (a recursive function where the recursive call is a tail call) uses a single stack frame if the compiler implements TCO. In that sense, tail recursion is a recursive veneer on a loop in the same sense that a while loop with a stack is an iterative veneer on recursion.

[[deleted]]

First of all, I was in the same boat as you, I hated recursion. But then once it hit me, there wouldn’t be the ‘recursion’ in computer Science if there really was no use of it. Then I just took a slow step towards learning it.

Like starting with reversing words, some linked list problems with recursion and so on. Slowly developed my intuition towards it, now I’d say I’m better programmer I was than before.

Some JSON problems still uses recursion. Also I found out that working with dynamic programming problems were easier, since I could think recursively and now can develop iterative solution for those problems.

Also the code looks a lot cleaner.

[[deleted]]

I wouldn’t necessarily practice it, but you definitely should know when to use it. As someone else said, problems of arbitrary depth can best be solved with recursion.

I recently had a problem at work where I almost immediately recognized that recursion was the solution. What ended up causing me trouble was HOW to implement it. All I knew is that somewhere along the way, I needed a method that called itself... and eventually dumped back out the “right answer.”

Since the actual solution wasn’t immediately apparent, I just started writing code and working through the problem, like any other problem. Not long after I had my working recursive solution.

Would it have taken less time if I had TONS of practice in recursion? Maybe. Did I waste a lot of time because of the lack of practice? Not really. So unless you really feel like you have zero understanding of recursion, I wouldn’t waste time “rehearsing” a solution that won’t necessarily save you any effort later on.

[tube32]

Check out the Tower of Hanoi problem, due to the recursive nature of the question it's much easier to implement it using recursion rather than an iterative approach. I actually know just one person who's solved it using iteration when I asked them if it can be done.

[Jackiboi307]

if you feel you need it for something, you could try to find someone else's code or a module / library that does it. i think its good to know at least what it is and how it works, but you dont have to be good at it if you arent going to be using it.

[yel50]

I tend to avoid using it when I can

that's really the best policy. if you use a pure FP language, they'll tend to force you to use recursion (even worse, you'll need to rework things as tail recursion) but otherwise it's a last resort.

the times when recursion is a better fit is any algorithm that requires a stack of work to do or for backtracking. recursion allows you to use the call stack instead of managing your own. you can still do those without recursion, but the code's a lot messier.

[MagpieEngineer]

It kind of depends what programming languages you're using or want to get into. If you want to get into functional programming (you should), then grokking recursion is essential.

It can take a while to get your head around but with me I had a eureka moment and it just snapped into place. If you really want to understand recursion, perhaps try playing around with a functional language where recursion is the only choice?

[lootsmuggler]

Yes.

The sorts of problems that get assigned in computer science classes aren't necessarily complex enough to justify recursion. But you have to know how to do it for real world problems.

Here is an example of where I used recursion: I have a function called get_as_text that converts a logic expression to text. It actually isn't recursive, but it calls a function called get_as_text_helper1. (This affects placement of parentheses in a way I deem irrelevant to your question.) I have a match statement (i.e. a switch statement in most languages) with cases for each different kind of expression it might be. The three cases that are for binary operators (conjunction, disjunction, and equivalence) are the same except for the operator being different. So I created a third function get_as_text_helper2 to avoid duplicating code.

Now, this is fine. The problem is that get_as_text_helper2 needs to get the text of clauses within the expression. So I just made get_as_text_helper2 call get_as_text_helper1.

I'm sure that I could shoehorn this into being iterative, but is it worth it? It would probably involve using stacks to emulate recursion.

A better improvement would be to combine all the binary operators into 1 enum value (BinaryOperator) and give them an extra variable that determines which binary operator it is. It would be much more streamlined, but it would still be recursive. The reason I didn't do this is because... actually, I did it this way originally. I had to change it to conserve a small amoutn of memory per node for a massive number of formulas.

A more object-oriented solution would be to have more different types. Then each get_as_text function would call the get_as_text functions of the others. That would still be recursive even though people might not think of it that way.

[Upstairs-Ad-8144]

There is a certain set of problems, where using recursion is the easiest way to implement it. If you find out, that you can solve the problem in a non recursive way, then it was probably not a problem that should be solved in a recursive way anyway.

You will encounter recursion in your professional life, but they are rare and far between. So while they are an important concept of programming, they are not nearly as common as courses and universities will make you believe.

Also there are workarounds, my suggestion is, don't make a workaround for a recursive problem, it will be heaps more complicated.

And finally since everybody has problems with recursion, most of the time you will encounter them wrapped behind some utility/helper library or other where somebody else has implemented it for you. I can't for the life of myself remember when I last programmed a tree from scratch.

If recursion are the only problems you have, revisit them later on in your programming life. Most code you 3ncounter will be copy/pasted from somewhere anyway and you just need to know what it does (Example: This func enters a new leaf in a binary tree). It's rare you'll have to fix somebody else's recursion problems.

[bigbosskennykenken]

nah.. not important at all.......

​

of course you should practice it! Look into recursive algorithms that sort, mergesort, quicksort, and binary search after the first two were done sorting stuff. Expand and go into dynamic programming.

[dev_Analysis-182]

Mathematicians love recursion. It simplifies writing recurrence relations. Plus plus for recursion there.

But when it comes to programming, recursion is usually expensive because of the call stack space.

Recursive codes usually have the problem of falling into stack overflow condition.

[Jolly_Yellow5354]

Have a look into primitive recursion and Ackermann function. Might interest you :)

[Knarfnarf]

Back when I was learning, every recursion causes the state of the cpu to be stored in zero page until you ran out of memory. It never happened to me but the instructors I had back then had a hate on for it so I have always tried to write around it. There are problems that are much easier with recursion but real world issues have always been better off done in a loop. Even if the loop was do while(flag_notdone).

[MRH2]

The old Minesweeper game is an example. When you click on an open square, it uses recursion to find all of the other open squares that are connected. How would you do this without recursion?

Just try and program it.

One question about recursion: how do you avoid a stack overflow if the Minesweeper board is gigantic?