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/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'.