Recursion ... is it needed?

Question

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

Answer 1

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.

Answer 2

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

Answer 3

Exact. Its powerful but its an option, not an mandatory choice.

Answer 4

Interesting question... I think sometimes recursion is the only way to solve a problem.

Answer 5

No, its an option but it is not needed

Answer 6

Very good question
I think that recursion is never needed, and it can use to enough cpu and memory resources.

Answer 7

I think is NOT needed, but it helps to solve problems

Answer 8

¡Good Question! Recursion It's useful but not essential

Answer 9

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 :)

Answer 10

yes in some mathematical equqtions

Answer 11

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.

Answer 12

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.

Answer 13

It's not needed, of course, but it's a very good way to auto call

Answer 14

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

Answer 15

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)

Answer 16

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

Answer 17

Recursive functions are easier to code, but more expensive in resources.

Answer 18

🤔 Most of the time it is optional; but when is possible to use the recursion, I like to use it to write clean codes...

Answer 19

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

Answer 20

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....... :)