+ 78

Recursion ... is it needed?

Recursion is powerful, true, but... is it needed? An algorithm that can be resolved using recursion, also can be resolved without recursion?

6th Dec 2016, 8:43 PM
Jose
169 Respuestas
+ 83
it is not needed. every algorithm that uses recursion can be programmed without recursion. U learn this in theoretical computer science of you're studying something like this (like me). however, some algorithms are faster or use less memory with recursion than without it. Or some algorithms are better readable. u also can show that every algorithm can be programmed using recursion. in short: you should always think about what problem you need to solve, then you can think about using recursion or not.
8th Dec 2016, 9:11 AM
Peter
+ 28
While not needed for a lot of languages, it is for other, purely functional languages. This is as purely functional languages do not allow any mutability. This means that "variables" can never change values. This seems like a big drawback but it has many benefits and causes a lot of bugs not to be able to occur in a language like this. Also, it is not true that iteration is faster than recursion. In many C-like languages, this is the case, but this is due to how they operate. In a purely functional language such as Haskell, you have really fast recursive functions due to the lazy evaluation. There are also ways to optimize recursive functions with tail call optimization. also, recursive functions can look way nicer than non recursive ones. take the Factorial function. The first, non recursive is in JavaScript: function fact(n){ var ans = 1; for(i=2; i<=n; i++){ ans *= i; } return ans; } here is a recursive way in Haskell fact 0 = 1 fact n = n * fact(n - 1) Even if you don't understand what the code does, you can clearly see that it is much easier to write a recursive function and clearer in a language like Haskell. in conclusion, while it might not be necessary to use recursion, it is helpful if you're trying to keep mutability out of your program, and also it can be as fast as iteration. it can also look a lot nicer in terms of code, so there are many reasons to use recursion
11th Dec 2016, 11:09 PM
Mark Williams
Mark Williams - avatar
+ 22
Exact. Its powerful but its an option, not an mandatory choice.
6th Dec 2016, 8:50 PM
Andrew Westow
+ 18
Interesting question... I think sometimes recursion is the only way to solve a problem.
6th Dec 2016, 9:24 PM
Aaron
+ 15
No, its an option but it is not needed
6th Dec 2016, 9:29 PM
Manolo
+ 13
Very good question I think that recursion is never needed, and it can use to enough cpu and memory resources.
6th Dec 2016, 8:55 PM
toreman
+ 11
I think is NOT needed, but it helps to solve problems
6th Dec 2016, 8:46 PM
Robert Johnson
+ 8
¡Good Question! Recursion It's useful but not essential
18th Dec 2016, 5:33 AM
Brayan Jeshua
Brayan Jeshua - avatar
+ 7
you're right, in terms of the outcome recursion is not needed, but in terms of performance and used resources recursion is a clear favorite - unless you can handle it :)
6th Dec 2016, 8:48 PM
codinator
codinator - avatar
+ 7
yes in some mathematical equqtions
18th Dec 2016, 6:39 PM
F.Heeh. 2nd Yr. Hebron University‏‎
F.Heeh. 2nd Yr. Hebron University‏‎ - avatar
+ 6
It is too necesary, in a Data structure and algorithm analysis course the biggest part of algoriths are recursive. Just one example, quick sort is one of the faster algorithm just n lg (n) time and it is recursive. However there is the implication high memory consumption, but memory and getting big and cheaper. Other cases: binary trees, B trees, red black trees and more.
8th Dec 2016, 8:27 AM
Johan Durán
Johan Durán - avatar
+ 6
yup.. without recursion also program can b built using loops but using recursive algorithms makes d code more readable. And considering the time complexity iteration(loops) is better than recursion.. But basically merits n demerits purely depend on the programmer who is using either of these methods.
8th Dec 2016, 3:09 PM
rossi
rossi - avatar
+ 6
It's not needed, of course, but it's a very good way to auto call
8th Dec 2016, 10:25 PM
Emily Podjatrowski
Emily Podjatrowski - avatar
+ 6
There are no "necessary" uses of recursion. All recursive algorithms can be converted to iterative ones. I seem to recall a stack being necessary, but I can't recall the exact construction off the top of my head. Practically speaking, if you're not using recursion for the following (even in imperative languages) you're a little mad: Tree traversal Graphs Lexing/Parsing Sorting
18th Dec 2016, 4:39 AM
The Artist Formally Known as Jeremy
The Artist Formally Known as Jeremy - avatar
+ 6
Any recursion can be implemented with loops. However, sometimes the recursive solution to a problem is easier and prettier (for example going through a tree structure)
18th Dec 2016, 8:51 AM
James Flanders
+ 5
Any problem that can be solved by loops can also be solved using recursion, and vice versa. However some problems have simple solution using recursion logic, while it would be very complicated using loops. Example Towers of Hanoi. You can avoid recursion unless your algorithm requires it
9th Dec 2016, 4:35 AM
Rishi Anand
Rishi Anand - avatar
+ 5
Recursive functions are easier to code, but more expensive in resources.
10th Dec 2016, 7:38 PM
wsw
+ 5
🤔 Most of the time it is optional; but when is possible to use the recursion, I like to use it to write clean codes...
18th Dec 2016, 1:06 AM
Rodrigo Abreu
Rodrigo Abreu - avatar
+ 5
You are right on recursion that it is useful in some cases. But When a recursion function is called it take a lot of memory stack in ram. Due to this it is slow. I said to avoid it because a function should use less memory as well fast. recursion is not fast and takes lot of memory than Iteration function. Memory are not unlimited, use it wisely. I don't know that you know data structure or not but When you learn it you have to take care of each byte. Each memory block is important. Hope you understand
18th Dec 2016, 1:39 AM
Aditya kumar pandey
Aditya kumar pandey - avatar
+ 5
Well... Recursion is not always needed.... There are 2 solutions to any algorithm.... 1. RECURSIVE SOLUTION 2. ITERATIVE SOLUTION Iterative solution is comparatively faster.... taking lesser execution time..... It involves use of multiple loops... which often makes the program quite long and complex.... and quite confusing to remember... Whereas...... Recursion takes longer time.. as when the function calls itself everytime... it has to store its current data... and stop its current execution .... which makes it slower...... but the program becomes very easy to code and simple to understand...... So overall... when you feel lazy... and want to do your work easy.. you should go for RECURSIVE solution... But when you are working on a big project that values Efficiency.... you should opt for ITERATIVE solution....... :)
18th Dec 2016, 5:54 AM
Apurva Tripathi
Apurva Tripathi - avatar