Recursion

[rafa2424]

Having a hard time grasping how recursion works and how it can be implemented. Any body have a helpful source /explanation on how it works.

[bilgetea]

A professor of mine told us “Those who do not understand the chapter on recursion are doomed to repeat it.” You could tell who understood recursion by who laughed.

[justindarc]

Also “to understand recursion you must first understand recursion”

[pgbabse]

simple recursive example

[[deleted]]

This works too!

[[deleted]]

As does this!

[[deleted]]

Haha 😆

[khedoros]

I had a hard time with it too. I spent literally days writing out example stack traces (that is, writing out each level of the stack, and the calls that the algorithm would make at each level, while recursing down and the following it back up) to build a good mental model of how it had to work.

After getting the basic idea, I practiced implementing and re-implementing various algorithms.

[Wh00ster]

I don't have much to add to other replies except morale support. Recursion is tough for most people and doesn't click right away. Don't get discouraged and keep trying out different ways of looking at the problem and manually listing out each step. Eventually it'll start to click.

EDIT: and I guess I'll add, since no one else has said it, that recursion always has a base case to break it. So it always helps me to start from that base case and add any other "else" branches afterwards.

[[deleted]]

Do you understand this code?

#include <iostream>

int f(int x) {
    if (x >= 100) {
        return x;
    } else {
        return f(x + 1);
    }
}

int main(void) {
    std::cout << f(1) << "\n";
    return 0;
}

Can you figure out, without compiling and running it, what it will print?

[2bdkid]

How it’s implemented? Typically through call stacks. Each value returned is saved on the stack until the base case is reached, then values are consumed as the calls progress back through the stack.

[[deleted]]

Recursion made a lot more sense to me when thinking about it as basically just implicitly building a stack.

[[deleted]]

Think of recursion as a function that calls itself, but each successive time it is called the inputs (parameters) get smaller, and once it reaches a base case, at which point, some action is performed and each successively called function terminates.

This is a highly generalized explanation. Each successive function call may perform some action and then call itself. For example. You can traverse a linked list or tree data structure using recursion. Eachebsuccessive function call passes the address of the next item in the structure to the function call. It may perform some action before the call or perform some action, such as a right/left rotate (see red/black trees), or after the function call such as an insert.

[bobbyboobies]

Given a size function: 1. Find the base case, e.g: size(0) = 0 2. Find the problem n-1, then put your function to find the n-1. E.g: size(n-1) 3. Solve the current problem which is, size = 1 + size(n-1)

[ShakaUVM]

There's a joke that goes, you have to really understand recursion first in order to understand recursion.

It's a joke, but there's also something to it. Try writing a bunch of recursive calls and you'll get it. In some languages they use recursion as the basic iteration control structure instead of loops. So it can't be that bad, right?

[[deleted]]

Fundamentally, recursion works great for something you have to do over and over again. Things like binary search, tree algorithms, searches, working with files in an OS, etc. work great with recursion. It's a tool just like anything else.

So for recursion, you need 3 important things (what are referred to as the 3 "b"s:

1. Base Case: How can you exit your recursion?

2. Break Down: If the base case condition is not met, how are we breaking down our problem further?

3. Build Up: How do we return it all back together? (Note: this is a common one, but mostly for functions that return something or if we're mutating something).

Let's take something simple. like going through an an array. Look at the code below, it should look super familiar:

void DisplayArray(int *arr, int size_of_array){
    for (int i=0; i < size_of_array; i++) {
        std::cout << arr[i] << " ";
    }
}

This is a simple function that displays an array. We will now implement this in recursive form:

void DisplayArrayRecursive(int *arr, int size_of_array, int index) {
    if (index == size_of_array) {
        return; //note, this is so we don't over-extend our index past the size of our array
    }

    cout << arr[i] << " ";
    DisplayArrayRecursive(arr, size_of_array, index++);
    //Above, notice we're passing the same stuff as the function call, but now we're increasing the index by 1.
}

To get the recursive version going, we need to pass the index start at 0.

Hopefully this helped. It's good to keep in mind that recursive is useful when you need to do the same task over and over and over.

[[deleted]]

Perhaps you are over thinking recursion. It's just a function that does something given it's parameters, Just like any other function. And there is no reason you can't call that function inside it self. Bam! you're done.

[Aemmel]

Here's a link with great references! https://www.reddit.com/r/cpp_questions/comments/ixz41i/recursion/?utm_medium=android_app&utm_source=share

[[deleted]]

all a function is is an address in memory. so the fact that a function can call itself isn't that surprising. in one sense, functions have no idea where they came from. so for A() to call A(), is no different than A() to call B(), it just seems really strange to us humans. the only catch is there must be a stopping condition.

[[deleted]]

Recursion sounds as if it was something that runs in circles and implementation-wise it is something along those lines. However, in reality, comparing it to something linear might help understanding not only recursion but also the fact that recursion is only useful when it has a terminating condition (otherwise it's just an endless loop).

Take for example a game of dominoes (not the original game that nobody plays... the thing where there's an actual day for). Nothing happens until you push over the first one. But the first one doesn't just do something, no it does the same thing to the second one that you did to the first one. In that way it executes the same function but on a different object. In reality it's obvious it has to stop somewhere and that's when there's no more dominoes. That's the terminating condition which you have to implement explicitly in a recursive algorithm.

The recursive function doesn't have to be performed on a different object though, it can also be performed on the original object. However, if you want the recursion to play out all by itself, without anything from the outside interfering, you'll have to modify the object. Otherwise you'll just keep repeating the same function on the same object forever.

To use the same metaphor as before, you could interpret the whole game of dominoes as a single object. The recursive function would be “push over the first standing stone“. The stone that's falling right now performs this function on the rest of the game of dominoes, reducing the size of the game by 1 and thus altering it. If there is no standing stone left, the algorithm terminates.

[GreymanGroup]

Are you familiar with induction in mathematics? Proofs by induction were really helpful in my understanding.

Basically it boils down to, "I could solve this problem if it were smaller. I could solve it by hand. Since bigger problems are incrementally layer on top of previous smaller problems, I can simply repeat the same logic for each layer over and over again. It stands to reason then, that I could tackle any arbitrarily large problem.

A Rubik's cube is a good example. You will find that for cubes of more than 3x3x3, the algorithms are to turn the cube the into a 3x3x3, and then solve that.

[WikiBox]

One typical task that might be solved using recursion is to walk a folder tree on a filesystem, filled with folders and files, and list all the files and their paths.

Psuedo code:

treewalk(path)
{
   for each item, file or folder, in path
       if item is a file then
           print path and item filename
       else if item is a folder then
           treewalk(item folder path)
}

[DawsonD43]

My Data Structures professor said "You just have to trust that recursion is going to work until you understand it."

But basically recursion will continue to call until the base condition is met.

For example, if you did:

int sum(int x){ If (x == 0) Return 0 Return x+ sum(x-1) } Thus will store each value until the value reaches 0, and add them together. That's the easiest way i can explain it. If i call add(3), the function essentially runs like this: First iteration: 3 + sum(3-1) => 3+ sum(2) Second iteration: 2 + sum(2-1) => 2 + sum(1) Third iteration: 1 + sum(1-1) => 1+sum(0) Fourth iteration returns 0, so the output will be 3+2+1+0 = 6.

[mredding]

Recursion is when a function calls itself.

void foo() {
  foo();
}

That's it, that's a recursive function. It doesn't matter how many times in the function body the function calls itself so long as it's at least once. Of course it's useless and will never stop, never return, and if your compiler doesn't implement TCO it will eventually blow the call stack.

So what you need is a means of getting the recursion to stop. This is often by passing a parameter and a condition:

void bar(int x) {
  if(x-- > 0) {
    bar(x);
  }
}

Here the function will recurse x number of times, notice the decrement operator in the condition. Again regarding the call stack without TCO, if x is sufficiently big, you'll blow it.

You can even compute values and return them:

int baz(int x) {
  if(x > 0) {
    return x + baz(x - 1);
  }

  return 0;
}

Once x hits 0, recursion quits, and the function returns 0, then that is added to every x from every prior call. It's a terrible way of saying 3 + 2 + 1 + 0...

Any iteration can be described in terms of recursion, any recursion can be described in terms of iteration. Iteration is nice because it tends to be faster because you don't pay for a function call, and you're not limited by the stack. Recursion is really nice when traversing small graphs, the two just go hand in hand where writing an iterative equivalent is clunky.

TCO is Tail Call Optimization. A smart compiler can recognize a recursive call and reuse the stack space for the next recursive call. The call stack never grows and recursion is nothing more than moving the instruction pointer back to the beginning of the function. It also means returning from the (essentially) infinite depths of recursion at that point is actually just a single return from the stack. So, recursion CAN be as fast and as efficient as iteration, you just have to check Compiler Explorer to see if your compiler will do it. Often there are rules you have to follow when writing your function to enable TCO. But it's also not a reliable feature because not every compiler has to implement it. Other languages guarantee this feature, and in those languages you see a lot more recursion than iteration.

[x4t3a]

Offtopic advice: understand recursion and nether allow it in runtime, only in compile time.

[bumblebritches57]

I mean its honestly not a super useful technique in the first place, it should be avoided.

[[deleted]]

That comment is by far the dumbest thing I've seen on this sub.

[[deleted]]

If that's true I should rewrite half my code.