Replace loops using recursion observation

I believe this statement in the challenge is incorrect:

However, notice that multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1] .

I think it should read:

However, notice that multiply(arr, n) == multiply(arr, n - 1) * arr[n ] .

  **Your code so far**



      **Your browser information:**

User Agent is: <code>Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.51 Safari/537.36</code>

**Challenge:**  Replace Loops using Recursion

**Link to the challenge:**
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/replace-loops-using-recursion

I think the original is right. Remember that arrays are 0-indexed and the value that we pass to the function is effectively 1-indexed. It’s confusing, but those are two different numbering systems.

1 Like

I get what you are saying, however let’s look at a different example. Say we are looking for factorial(x), which for x=5 would 54321 = 120.

factorial(x) in this case is equal to factorial(x-1) * x or 432*1 * 5 = 120.

The is what is written in the code camp challenge:

factorial(x) = factorial(x-1) * (x-1) or 432*1 * 4 = 96 which is incorrect.

That is the recursion formula I was looking at when I realized something may be amiss, or more explicitly:

https://www.freecodecamp.org/news/how-to-factorialize-a-number-in-javascript-9263c89a4b38/

function factorialize(num) {
  if (num < 0) 
        return -1;
  else if (num == 0) 
      return 1;
  else {
      return (num * factorialize(num - 1));
  }
}
factorialize(5);

The is what is written in the code camp challenge:

factorial(x) = factorial(x-1) * (x-1) or 4 *3* 2*1 * 4 = 96 which is incorrect.

No, you are confusing the number with the index.

Let’s think mathematically, not code. Let’s assume 1-indexing.

We have a Product function that takes a set and multiplies its elements.

Product(our set) = Product(our set without the last element) * (our set's last element).

(again, this is math, not code)

If we create a Set function that will accept return either a range (two parameters) or a value in a set (one parameter).

So, if there are 5 elements, we could rewrite this as:

Product(Set(1, 5)) = Product(Set(1, 4)) * Set(5)

OK, let’s make it more generic, n is the number of elements.

Product(Set(1, n)) = Product(Set(1, n-1)) * Set(n)

Now, rather than our Set function, we just have a set called set as the first parameter to Product and how many elements to multiply as the second:

Product(set, n) = Product(set, n -1) * (last element of set)

So if we switch back to JS, and we think of set as an array_, how do you get the last element of an array? It’s length minus 1.

multiply(arr, n) === multiply(arr, n -1) * arr[n - 1]

Again, the first n - 1 is referring to a length. If n is 5, then it is referring to the length of the array, 5. So it is telling the next iteration to reduce that by one. But as the array index, n - 1 is not reducing anything. It is referring to the nth element of the array, because it is 0-indexed.

But if you don’t believe me, just test it yourself. Try this code:

function multiply(arr, n) {
  if (n <= 0) {
    return 1;
  } else {
    return multiply(arr, n - 1) * arr[n - 1];
  }
}

console.log(multiply([1, 2, 3, 4, 5], 3))
// 6

If I change it to the code that you are suggesting, it will not work anymore. It
gives the wrong answers. That is the most important test - what works. Put in some log statements and see what is happening. Pay very close attention to what arr[n - 1] is.

Recursion is confusing. 0-indexing often trips people up.

Actually, now that I think about it, arr[n] can’t be right. If n is the size of the array, that value will be undefined (or garbage). When I run that, I get NaN as the final value.

1 Like

After looking at this some more, I realized you are correct. Thanks for the e-mail…

Dave

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.