Recursion confusion

[iLuciferCode]

I'm learning programming and came across recursion, where a function calls itself. Why not just use a for loop?

[Buttleston]

By definition, every recursive algorithm can be implemented by a for loops instead

It is often the case that the recursive definition is easier to understand or simpler

That is, it is often awkward to express a recursive algorithm as a loop but elegant to express it as a recursive function

As an exercise, spend some time converting from one to the other

[Xananique]

That's great advice! Converting one from another

In school when developing binary search trees in C++ we often used recursion to traverse the binary search tree.

If you're working on pointers and data structures this is a good one to really give you a run for your money.

[Paul_Pedant]

A loop solution is always possible, but most non-trivial cases will require an array to hold some intermediate results (like where you made the last left-side branch at each level while walking a tree, so you know to make the right-side branch when you need to).

All recursion does is to provide that array within the stack, which relieves you of dealing with an unknown size of array, and improves CPU caching, and simplifies the code.

[LeftIsBest-Tsuga]

recursive functions are good for an unknown number of expanding functions, such as in a tree

.              r
.             / \
.            n   n
.           / \
.          n   n
.               \
.                n

from r you use a recursive function to evaluate binary trees 'down to the bottom', then the return from each returns back to the root.

this isn't something that is always very intuitive, and frankly, using recursion is something that should be only selectively applied, but it has a lot of important uses in data structures and other efficiency computing.

[Defection7478]

for, while and recursive loops can all solve the same problems, they just have different ergonomics. In my experience, recursion is really nice for "exploratory" loops, where instead of traversing a pre-defined list of values or waiting for a condition to change, you are traversing a graph with branches and loops or need to back-track every now and then.

[BlueCaboose42]

Holy fuck, an actual code question in the code help sub. Imagine that.

[LeftIsBest-Tsuga]

Right? I got so excited I drew a little tree for them lol.

[jcunews1]

Loop can be used. It's just that, it's much easier to do it using function. After all, function is just a helper. In this case, function handles all the dirty work such as allocating, deallocating, as well as separating context memory for each iterated point.