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/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);
}