ANSWERED ◇ Recursion VS for Loops ◇ All languages

Question

Instead of doing the examole sololearn gives on recursion, why wouldn't you just do this.

//in c++
int factorial(unisgned n){

for(unisgned i=n-1;i>=1;i--){
n*=i;
}

return n + !(n);
//not(n), in case n==0 ( 0! =1)
}

I can't think of an example that recursion is better than for's. I mean they are harder to think and might take a lot more lines of code!

Answer 1

xaralampis_, I have often heard the statement that recursion was really easy to think about, and also frequently shorter, than iteration.

Personally, I found recursion harder to wrap my head around, it took some practice.

I think I would still tend to iteration, but there are some cases where recursion seems to be more easy to write, like a permutations function or a qsort.

I think more important to what's most readable to you or is a bit shorter, I think the actual performance should in most cases decide what you use.

Depending on what you do, recursion can have a high memory cost, and the depth may be limited, by default (like in Python or JavaScript) or by stack size.

I've heard that some languages are optimized for recursion, but I don't know much about that.

Answer 2

In functional programming languages such as Haskell, everything is immutable, technically you have no variables, everything is achieved by function calls. That's when you have no other way but use recursion.

For this reason these languages usually support "tail call optimization" in recursion, that means the output value of the function is passed to the next recursive call in the very last step. This saves memory because earlier calls (iterations) do not need to be kept in memory anymore. Python doesn't do this, that's why recursion is limited to a certain depth.

Answer 3

Tibor Santa Yeah I read some of these information but the fact that it is a 'chapter' in many other languages really confuces me. I have been coding for 2 years or so and I've never run into the need of recursion.

That's until i wanted to check a bunch of shorting algorythms. After the description of every single one of them, there was a small code section in c++ for copy paste. Most of them used recursion. It was really hard to understand what did the code and I just asked my self 'Why recursion'.

I mean, I'm quite more comfortable with it now but I still haven't understood the use of it. Just like the pointers back then.

Answer 4

Some problems which are typically best solved with recursion, involve hierarchical relationship of objects, where the depth of hierarchy is unknown upfront.
For example think how you would implement a program that lists the content of a folder in the filesystem, listing also each subfolders content and so on.
Or you want a map of facebook connections, and friends of friends, up to 5 levels. You could write 5 nested for loops, but what if you need 15 levels later?

Answer 5

unsigned должно быть
https://code.sololearn.com/c1MeL50VdGZf/?ref=app

Answer 6

Could even do it like this:

long long fact(int n) {
return n<2? 1: n*fact(n-1);
}

Answer 7

HonFu and Kairat Soltanalinov, sure i could wright this specific code really compact.

But the point is that if the algorythm is more complex e.x. a shorting algorythm, it can get a lot harder to think about it, read it from someone else, and can take more space as well!

For loops on the other hand are just repeating code.

Answer 8

Hey