+ 3

right Recrusion mindset ?

i know that recrusion and itteration is basicly the same. but for quite sometime i realize that recrusion is almost always the least thing i can think of when solving a problem, unless i've read in books/web/other's code about certain problem is much easier to solve using recrusion. on the other hand whenever i think about "i need to repeat this step again to solve this" my mind just straight thinking which loop i need to use. is there any rule of thumb on what kind of situation/problem to use recrusion over just normal loops ? thx.

5th Oct 2019, 6:19 AM
Taste - avatar
6 Answers
+ 6
Some problems can be seen easily solvable by recursion and some by simple loop, conversion is possible in some cases but in most cases it is hard and probably not possible. Problems involving backtracking(where we need to undo our previous move if required result is not reached in next steps) will require recursion only, you can't do it with loop. Now for loops to recursion, you can think of doing some task involving 3 loops, now writing recursion code for it will be little hard. (you can see my 3 SUM code as example) when you see that you can breakdown a problem into a smaller problem of same type you can use recursion, else use loop for doing repeating same task.
5th Oct 2019, 6:52 AM
Gaurav Agrawal
Gaurav Agrawal - avatar
+ 3
Gaurav Agrawal What you say about backtracking is not quite right as there are also iterative versions of backtracking algorithms like for example dfs. They use while-loops instead of recursion if I remember correctly. In principle you can solve any problem iteratively or recursively. Otherwise you wouldn't be able to base whole languages on it as [user id="5433682"]~ swim ~[/user] rightly states. Most of the time you will choose iteration though because it is usually faster and takes less memory.
5th Oct 2019, 8:20 AM
Thoq! - avatar
~ swim ~ And when you will stop struggling with recursion - and I haven't too, the next step will be Y-combinator: nearly understandable for me... https://mvanier.livejournal.com/2897.html
5th Oct 2019, 9:24 PM
Bilbo Baggins
Bilbo Baggins - avatar
I don't know this is correct to post in this thread. Recursion in general working only if it's an right direction recursion. If it's an left recursive function then compiler will generate error or overflow or stop the flow due to deadlock condition Left recursive function in any language is avoided by compiler as in this an function let's say A(){ A(); } In above when function A() calls and start execute the body of function then it again see A() function which again call the function A() in this type of situation that grammar or language produce left recursion which is not solvable so during recursion we take care of this situation by doing left factoring and eliminate the left recursion and convert it into right or general recursion which is solvable. Except of left recursion every recursion which is generally of three type left, right , general
6th Oct 2019, 2:12 PM
Preity - avatar
Many persons will write a lot of things but basically for the purposes of space and coding time, recursion is better. But if its running time you are interested with, iteration is best.
6th Oct 2019, 2:27 PM
Nkiangmatiah Junior
Nkiangmatiah Junior - avatar
No there is no rule for when we use recursion or not. It's totally depends on you and your coding problems. If you think you can make code with recursion then it's good and fine. And recursion also make code easy to understand and improve modularity. So it's good for practice to use recursion in our code 👍good luck keep coding.. 😊
7th Oct 2019, 2:10 AM
‎‏‪‏‪Girish Patel‬‏‬‏‎
‎‏‪‏‪Girish Patel‬‏‬‏‎ - avatar