Why use recursion in C #?

Question

Just got close to the use of recursion, and almost immediately a question came up.

In the video course and the texts that I managed to study, the advantage of using recursion is a shorter record. In this case, for example, the factorial cycle is described not much longer, and the recording is guaranteed to be understood by the majority of programmers who will read it. To understand recursion, you must first understand recursion.

On the other hand, measurements of the execution time showed that there is no difference in the calculation of factorial (small, true).

But if you describe the addition of, say, a collection of integers, the difference is huge, and not in favor of recursion.

I admit that I am describing crookedly, but so far nothing has given birth to me. So, there is a class SomeNums that implements IEnumerable (int); it has a num list that stores the set itself.

Here is the loop:

public int CycSum() { int acc = 0; foreach (var num in nums) acc += num; return acc; }

Here is the recursion:

 public int RecSum (int step) { int acc = 0; if (step == 0) return nums[step]; return acc += nums[step] + RecSum (step - 1); }

And here I am somewhere in Main doing this:

 var n = new SomeNums(Enumerable.Range(1, 1000));

And then I measure the time and make a hundred times the addition of each of the methods. I consider the average, and (quite expected, in general) I get the conclusion:

Mean time for recursion: 0.034 468
Average cycle time: 0.006 387

And, of course, if I try to increase the number of members of the set, I get a stack overflow.

I understand that using recursion in the way that I do is incorrect. But are there any correct ways? In general, is there any point in using recursion in C #?

And yes, I know that there is LINQ with its Aggregate, but the post is not about that.

There are data structures with which it is more convenient to work with cycles (for example, arrays), and with others it is more convenient to use recursion.
For example, to traverse a tree with homogeneous nodes, it is convenient to write a function that accepts a node, performs calculations on it, and then calls itself for each descendant.
In general, the question of the appropriateness of the use of recursion is quite controversial, and clear recommendations about where and when it should be applied in the general case are difficult to formulate.
Just try to apply it to solve different tasks at the training stage in order to “get a hand”.
In practice, the decision that it is advisable to use recursion can be made on the basis of the specific conditions of the problem.
The problem is solved, but even in such a simple task, you can swing at writing without recursion.
As for "understanding recursion" ... A matter of taste - it's usually easier for me to write something with recursion than without it - it’s clear where it applies :)
Interestingly, I did not even think about trees when I wrote a question.
This, of course, is my fault, but if examples with a tree (or any examples at all, where recursion is obviously better than the cycle) were in the training materials, it would be much easier to understand.

Accepted Answer · 2016-11-01T03:14:18

There are data structures with which it is more convenient to work with cycles (for example, arrays), and with others it is more convenient to use recursion. For example, to traverse a tree with homogeneous nodes, it is convenient to write a function that accepts a node, performs calculations on it, and then calls itself for each descendant.

In addition, recursion is often used in algorithms, where the result of the calculation depends on the result of the same function called with other parameters or where it is difficult to pre-set the number of iterations. For example - quicksort . Even mathematical formulas can be expressed using a recurrent formula . Take the same factorial:

This explains why factorial computing is so popular in educational materials.

In addition to the advantages, recursion has some known disadvantages. One of the most famous problems mentioned in the question. If the recursion depth is too large, a stack overflow occurs, since when the function is called, its arguments and return address are placed on the stack, the size of which is finite. Modern compilers can solve this problem, but for this it is necessary that the recursive function be implemented in a certain way. So, if the call itself is the last operation of the function, then the compiler will be able to deploy recursion in a normal loop. This technique is called tail recursion .

In general, the question of the appropriateness of the use of recursion is quite controversial, and clear recommendations about where and when it should be applied in the general case are difficult to formulate. Just try to apply it to solve different tasks at the training stage in order to “get a hand”. In practice, the decision that it is advisable to use recursion can be made based on the specific conditions of the problem.

By the way, I copied the example from Wikipedia to VS, and still got a stack overflow.
Do I have something not included, or is C tail recursion shaped differently?
@eastwing in C # in debug mode, tail recursion is not optimized.
Actually, in order to properly penetrate, it was enough to realize the tree yourself.
Already at the stage of "design" I began to suspect something

trydex trydex 2,732 1 golden mark 7 silver marks 33 bronze marks · Answer 2 · 2016-11-01T03:46:02

Here is a good example of a toy.

There is a field with squares of different colors, and when you hover the cursor, all the single-color squares that come in a row vertically and horizontally are highlighted. And on click, they disappear and the field structure changes.

That is, here there is a recursive survey of each cell and the search for its monochrome neighbor, from which a search also takes place, etc.

Without recursion here it would be difficult to do.

It is very simple to do without recursion here, the only question is which algorithm is more familiar.
@Pavel Mayorov, Can you describe the algorithm without using recursion?

Why use recursion in C #?

2 answers 2

More articles: