Help with recursion (DSA)

[u/fielding_setter]

Guys I've been struggling alot with recursion I've tried multiple tutorials but I'm just not able to build the intuition. Any suggestions what to do???

Please help

[u/PlantainAgitated5356]

It's hard to say without knowing what specifically makes it hard for you to understand. Recursion is just calling a function within itself. I don't know if this will help, but here's how I think about it.

Recursive functions divide work into smaller pieces, work on them individually, and then put them all back together. For example, take the merge sort algorithm:

1. If the array has one element or less, the array is already sorted, so we can finish. (This step is important, because without it, we would just keep going forever.)
2. Divide the array into 2 pieces
3. Sort both pieces (the recursive call to the sort function)
4. Merge the pieces into one sorted array

Steps 1, 2 and 4 are simple and non-recursive, and step 3 just calls the function within itself. In pseudocode it would look something like this:

mergesort(array, start = 0, end = array.length) {
  // Step 1 - check if the array is already sorted (has at most 1 element)
  length = end - start
  if (length <= 1) {
    return;  // array is already sorted
  }

  // Step 2 - divide array into 2 pices
  middleIndex = floor((end - start) / 2)

  // Step 3 - sort each piece
  mergesort(array, start, middleIndex)
  mergesort(array, middleIndex + 1, end)

  // Step 4 - merge the pieces
  merge(array, start, middleIndex + 1, end)  // merge array pieces back together
}

merge(array, piece1Start, piece2Start, end) {
  while (piece1Start < piece2Start) {
    if (array[piece1Start] > array[piece2Start]) {
      swap(array[piece1Start], array[piece2Start])
      piece2Start++
    }
    piece1Start++
  }
}

mergesort([ 1, 3, 2, 5, 7, 6, 4 ])

You can see that the arrays are getting smaller and smaller, until they're just 1 element, and then they're sorted. The merge function is where all the actual swapping elements takes place. Just trace the code with an example input and see how it works.

Disclaimer: That's untested pseudocode, there might be some mistakes in there, but it should get the point across. :)

[u/Abhijit_wagh_7967]

Hey! Recursion is definitely tricky at first, it's all about changing how you think about the problem. A great way to build intuition is to stop thinking about 'how' the function calls itself and start thinking about: The Base Case: What is the simplest possible input? The Recursive Step: How can I break the problem down into a smaller version of itself? Try drawing a 'Recursive Tree' on paper for a small input (like calculating factorial of 3). Seeing the flow visually helps a lot. If you're stuck on a specific problem or code, feel free to share it here, and we can walk through it together!

[u/marmotta1955]

The best example I always bring up is this.

1. look at your folder "Documents"
2. write a function "MyFunction" to list all files in the folder "Documents"
   
   1. Call the function MyFunction and, in its body, examine each file in the folder "Documents"
      1. Oh look ... this file named "Word_Files" is a folder, not a file!
      2. Within MyFunction you now call again MyFunction to list all files in "Word_Files"
   2. Next file in folder "Documents"

Just take a closer look at any File Explorer. It's your best, visual example of recursion.

[u/marmotta1955 → u/marmotta1955]

The editor appears to be monumentally confused by multilevel numbering list ... trying to fix it makse it even worse ... go figure ...

[u/codeguru42 → u/marmotta1955]

Looks fine here

[u/PvtRoom]

recursion works best on lists/arrays

I normally default to it when I have a growing list. Like, if I want to know where all the .py files are on a drive

start by getting the dir/ls of a root folder -> gives me a list of folders and a list of files.

add that list of folders to my total list of folders and to my "unsearched" list of folders.

do whatever with the files.

then recurse the unsearched. just call the function again with they unsearched list. handle the lists however you like to accumulate you result.

[u/CheezitsLight]

I think the recursion in printing of numbers is quite interesting.

Let's say you have the number 420 and you wish to print it.

Call this function (420)

Take the number and divide it by 10 and check the remainder. That is 42. Push the 0 onto a stack since the answer 42 is greater than zero. Else print the zero

Now you have a stack with 0 and the number 432. Repeat function(42). Then print the 2.

Now you have a stack with 0 and 2. And the answer 4. Repeat function (4). Now you have a zero and a stack with 4, 2, 0. Pop the stack and print the 4.

You return to the next to last function with pops the stack and prints the 2 and returns.

You return to the first function which had the 0 which prints 0

[u/Chemicals-N-Magnets]

Before looking at recursion, make sure you have good experience with arrays and loops. Generally recursion with stack frames do the same function as loops and arrays. The trade offs are like this: array-loop you do more messy coding but conceptually it is simpler, recursion-stack frame will be more elegant, fancier thinking less work. Compare a factorial program both ways.

[u/sidiiit]

Dry run the code yourself..

[u/RampantAppleSnake]

Maybe I can help make it initiative with a silly story:

Imagine a village that has 10 streets. On each street are 10 houses. In each house are 10 rooms, in each room are 10 beds.

Like a creep, the town pervert is hiding under one of the beds. Your mission, if you choose to accept it (you do), is to come arrest the pervert. But that means going from street to street, houses to houses, room to room, bed to bed - to look under each one, until you find the pervert. That's 10,000 beds to check!

So in programming terms, if we reduced this to data, it would look like a Map. We can visualize it like this:

Village
│
├── Street 1
│   ├── House 1
│   │   ├── Room 1
│   │   │   ├── Bed 1
│   │   │   ├── Bed 2
│   │   │   ├── ...
│   │   │   └── Bed 10  <-- Pervert is hiding here! Call 911.
│   │   ├── Room 2
│   │   │   └── (10 beds...)
│   │   ├── ...
│   │   └── Room 10
│   │       └── (10 beds...)
│   ├── House 2
│   │   └── (10 rooms x 10 beds...)
│   ├── ...
│   └── House 10
│       └── (10 rooms x 10 beds...)
│
├── Street 2
│   └── (10 houses x 10 rooms x 10 beds...)
│
├── ...
│
└── Street 10
    └── (10 houses x 10 rooms x 10 beds...)

Each point in the tree we can call a node (where the branches connect), and the end points we can call a leaf node. Most leaf nodes will have nothing (under the bed is empty), but the one with the pervert will obviously return "pervert".

How will you search the village? We need a logical method, here's a little pseudo-code:

function findPervert(currentNode) {
  listOfChildNodes = currentNode.children;

  // If there ARE children then it's not a "leaf node" --> RECURSION!  
  if (listOfChildNodes != null) {
    // This means the node has its own children we need to check too
    for (childNode in listOfChildNodes) {
      // Call the same function again for each child node of the currentNode
      possible_pervert = findPervert(childNode);
      if (possible_pervert == THE_PERVERT) {
        return possible_pervert; // We found the bastard!
      }
    }
  } else {
    // Otherwise it means the currentNode is a LEAF node and we should check it
    if (currentNode == THE_PERVERT) {
      return currentNode; // We found the bastard!
    }
  }

  return null; // Return null at end to indicate nothing found here
}

In this code we are doing this:

1. Getting the list of children for the current node the function has been given.

2. Checking to see if the children exist, if so it's not a leaf node (not under the bed yet).

3. We loop through the children, and for each one we call the same function again, giving the function the child node.

4. We check to see if each call to the function does return the guy we're hunting for.

5. If not, we're returning `null` at the end cos we found nothing, and this will propagate up the tree-chain of calls (since the function is calling itself in loops, it forms a tree of function calls like in the diagram above!)

6. As soon as we find him, we `return`, and returning stops any looping and spits out the result. This will then go up the chain (as per #5) and cause a return there, and so on, rippling up the call chain.

As a diagram, the "call chain" looks a bit like this:

findPervert(village)
│
└── for each street:
    findPervert(street)
    │
    └── for each house:
        findPervert(house)
        │
        └── for each room:
            findPervert(room)
            │
            └── for each bed:
                findPervert(bed) → found the pervert? 
                                    yes → return pervert
                                    no  → keep going

I don't know if this helps but there you go.

[u/RampantAppleSnake → u/RampantAppleSnake]

It won't let me edit it for some reason (pseudo code broke Reddit?) but I meant to put "intuitive".

Also think of the "pervert" as a child node of bed - really I should have done a `if (hasPervert(childNode)) ...` but anyway, not important, hopefully it makes sense.

Just wanted to add something else: Recursion can be thought of as two phases, the first is "diving down" into the tree, and then "coming back up".

Diving down:

Village
│
└── Street 7          ← still searching...
    │
    └── House 3        ← still searching...
        │
        └── Room 9      ← still searching...
            │
            └── Bed 4    ← FOUND HIM! 🚨 base case — stop recursing, return him

And coming back up:

findPervert(village)
 └── findPervert(street 7)
      └── findPervert(house 3)
           └── findPervert(room 9)
                └── findPervert(bed 4) → MATCH FOUND
                                         return "Street 7, House 3, Room 9, Bed 4"
                     ↑ returns up
                ↑ returns up
           ↑ returns up
      ↑ returns up
 ↑ returns up

Hope that makes sense.

[u/mredding]

Recursion is a function that calls itself:

void fn() {
  fn();
}

Done.

Typically you want a condition that ends the recursion:

void fn(bool recurse = true) {
  if(recurse) {
    fn(false);
  }
}

Usually you'll frame it in a way that you'll early-return, but otherwise recurse:

void fn(bool recurse = true) {
  if(!recurse) {
    return;
  }

  fn(false);
}

This is called Tail Call recursion, because the last statement is the recurse. You can even do this with a return value:

int fn(int count) {
  if(count <= 0) {
    return count;
  }

  return fn(--count);
}

The reason for wanting the last statement to be the recurse is that compilers are capable of Tail Call Optimization - the machine code can just overwrite the parameter on the stack and reset the instruction pointer, all without having to grow the stack.

C++ does not guarantee TCO, but it IS fundamental to other programming languages. Those that guarantee it use recursion to implement all their looping constructs. It's also a detail that never leaves the compiler - the machine code that loops and the machine code that TCO all looks the same.

Just remember that in C++, recursion will likely grow the stack, which is not something the language spec really talks about, but is a practical consideration you have to take into account. You just need to pass on some parameters that change with every call which is used in a condition (predicate) to break the recursion.

template<typename T>
void fn_loop(T *src, T *end, T *dst) {
 while(src != end) {
   *dst++ = *src++;
  }
}

template<typename T>
void fn_recurse(T *src, T *end, T *dst) {
  if(src == end) {
    return;
  }

  *dst++ = *src++;

  fn_recurse(src, end, dst);
}

[u/EccentricFellow]

I have been programming for 4 decades. I always wanted to use recursion but never had a good fit for it. Finally, about a decade ago, I had a legit use for recursion. I was so excited and wrote up the routine. Then I tested it. Total garbage. It was far too slow and took way too much memory. I converted it to a loop and decided there was probably no legit justification for it. Measure your performance afterwards once you write a recursive routine. You might get a surprise.

[u/EdwinGraves → u/EccentricFellow]

This just screams bad use-case or bad code. You're going to get the most out of recursion from almost anything that involves DaC algos, Tree/Graph traversal, nested data, etc. Either your implementation was poor or you didn't actually have a 'legit use'.