How do I effectively count iterations when using recursion?

[krisb1220]

Most of the code challenges that I see (on and off FreeCodeCamp) that require recursion do not give you a third variable to manage the iterations. On top of that, most of the challenges would heavily benefit from that third variable.

For example, take the twosum problem on Leet Code. It only allows for two variables, an array and a target. Without the third variable it becomes pretty hard to manage the recursive iterations without getting super clunky and confusing (I chose to append the iteration count to the array inside of a second array). This adds alot of stress that otherwise wouldn’t be needed if they just allowed a potential iteration variable.

Am I missing something here?

[JeremyLT]

You rarely need use recursion to solve a problem. If you need an iteration count, that’s a sign that you should be using a loop.

[krisb1220]

Got it, thanks for the tip. What if it required a nested for loop? I feel like they get clunky and confusing. Just bite the bullet and nest?

[JeremyLT]

Sometimes you just need to nest. For the two sum though there is an algorithm with a single pass, if I’m remembering the problem correctly.

[krisb1220]

Gotcha. I’ll just have to get a bit more creative. Thanks!

[DanCouper]

Just as an FYI for Leetcode: because passing a challenge is based on the execution speed, it’s unusual that a[ny naïve] recusive solution will work if you use JavaScript. It will work fine if you use Erlang or Elixir (and I assume Scala as well), but not for languages that don’t have the optimisations required to make recusion as performant as imperative looping.

So for example, here is a recursive solution, I think fine to post because it just will not pass (was hitting ~400ms before I got an out of memory error every time I tried to submit it). It works perfectly fine [given no time limit], but it’s no use in the context of Leetcode:

function twoSum ([head, ...rest], target, headIndex = 0) {
  const sumIndex = rest.indexOf(target - head);
  return (sumIndex !== -1)
    ? [headIndex, sumIndex + headIndex + 1]
  	: twoSum(rest, target, headIndex + 1);
}

Edit: exact same solution in Elixir, passes fine (not particularly efficient, but works every time I hammer submit):

defmodule Solution do
  def two_sum([head|rest], target, head_index \\ 0) do
    case Enum.find_index(rest, fn x -> x + head == target end) do
      nil -> two_sum(rest, target, head_index + 1)
      x   -> [head_index, x + head_index + 1]
    end
  end
end

Edit edit: also fyi

@krisb1220

On top of that, most of the challenges would heavily benefit from that third variable.

You can have as many extra arguments as you want as long as the function can be executed with the expected number of arguments. So in practice, this means you normally initialise them with a default

function someChallenge(
  requiredArg,
  myOtherArg = "fine",
  anotherArg = "also fine",
  yetAnotherArg = "still fine"
) {
  ...

[krisb1220]

Awesome! I had no idea that time was a constraint, nor that I could pass extra variables. Thanks man!!