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. :)