Recursion n-1 checking understanding

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

This had me flummoxed for a while, but I (think) I understand it now. Can someone help confirm if I’m on the right track or give me some pointers please?

I believe it’s to do with the index numbers.

We think value 1, but the computer starts from value 0. Here’s some pseudo code

// n is a stand in for the length of arr

n (item 1) = 1  //human count
n (item 1) - 1 = js index //js count

Which means length of array will always be human count - 1… Have I started to understand it?

Link to the challenge:

That is true but it has nothing to do with recursion. That is just how arrays work. For an array, count will always be the same, human or JS. The difference is indexing - humans tend to 1-index while computers and computer languages tend (afaik) to always 0-index.

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

What that is trying to say is that the function is self-referential. It’s like a fractal. Or sometimes they’ll have a silly magazine cover of a guy holding a magazine whose cover is him holding a magazine whose cover is him holding a magazine whose cover is him holding a magazine … Or like in Inception, where they can incept a dream inside a dream, inside a dream, inside a dream … Or like when in high school you all got stoned and someone said, "Dude, what if the atoms in our bodies are just little solar systems and there are little people living there and their atoms are just little solar systems with people and their atoms…

These are examples of one dimensional recursion. And arrays are one dimensional data objects.

So, back to the above quote. What it is saying is that if you have an array like:

const arr = [2, 5, 4, 3]

and we have a function called multiply that will multiply the first n elements, then

multiply(arr, n)

should be the same as

2 * 5 * 4 * 3

and

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

is (substituting in)

multiply(arr, 3) * 3

so really, that is saying

2 * 5 * 4 * 3 === (2 * 5 * 4) * 3

which is the associative property that we all leaned in grade school (and then most of us forgot.)

but notice that here that this:

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

is calling itself - the function call on the right side is calling itself on the left side, but with a decremented n. So, what if we continued our expansion on the right side. We start with:

multiply(arr, 4) == multiply(arr, 3) * arr[3] 

becomes

multiply(arr, 4) == multiply(arr, 3) * 3

expands to

multiply(arr, 4) == (multiply(arr, 2) * 4) * 3

expands to

multiply(arr, 4) == ((multiply(arr, 1) * 5) * 4) * 3

expands to

multiply(arr, 4) == ((((multiply(arr, 0)  * 2) * 5) * 4) * 3

Now we reach the place where we want to stop because we have worked through the array. This is called the “base case”. This is the point where we have reached the end and we want to stop making recursive calls and start returning things.

Keep in mind that not a single function call has completed. The couldn’t complete because they couldn’t return until the next function call was complete, on and on. We have a bunch of incomplete calls on the call stack. But now we are at the base case and can finally return something:

    if (n <= 0) {
      return 1;

So we get:

multiply(arr, 4) == (((((1)  * 2) * 5) * 4) * 3

We can remove the parentheses because of the associative property and we can remove the 1 because of the associative property and we can get rid of the 1 because of the identity property of multiplication, so we are left with:

multiply(arr, 4) == 2 * 5 * 4 * 3

which is what we wanted. Note that the right side no longer has any function calls, so it can complete. The call stack will “unravel” and those calls stored on the call stack will return a value so each incomplete call will complete and return a value to the call below it so that it can complete and return a value to the call below it so that … on and on until all the function calls are complete and we have our answer.

Is this complicated? Yes. Is it weird to think this way? Yes. Will it take a (long) while to fully understand? Yes.

Do we need recursion? Not really. There is no problem that can be solved with recursion that can’t be solved without recursion.

Wait, then why learn it?!?!

  1. It is excellent training for your coder brain. It requires a deeper understanding of data structures and algorithms and how functions work.

  2. The sometimes show up on interviews.

  3. There are types of problems that are soooo much easier to solve with recursion. These often involve data structures like linked lists, trees, and graphs.

But don’t get frustrated. Do your best, realize that this is difficult stuff, and accept that understanding recursion will be a longterm goal.

2 Likes

Well, yeah, but not quite, cause the human count is also beginning with 0, but yeah it’s that kind of logic. But it doesn’t have nothing to do with recursion, it’s just how array works. What every recursion needs is the condition when it stops and it depends on what you want it to do. For example, if you have function to iterate through array, in iterative function you would use for loop such as
for(var i = 0; i < array.length; i++) {
//do something
}
In recursion, condition to end function would be either when counter is -1 or when it is equal to array.length. What I would put is
if(n < 0)
return 1
or
if(n == array.length)
return 1
Since you are multiplying you should put “return 1”, since it won’t change it’s value.
I hope I understood your problem and I hope I was helpful! :slightly_smiling_face:

1 Like
let specialArray = [2, 5, 4, 3]

  function multiplyRec(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiplyRec(arr, n - 1) * arr[n - 1];
    }
  }
console.log(multiplyRec(specialArray, 4))

So in this

return multiplyRec(arr, n - 1) * arr[n - 1];

multiplyRec(arr, n - 1) is the recursive call back. This is what controls the descent of index (n)?

Could I think of it like this.

(specialArray, 4)
index 4 !==0
recursively call until you get to 0
When base case index 0 is met return 1
index 0 = 2 in array

With the base case met and evaluated, the return 1 can be passed to the previous (specialArray, n - 1) * specialArray[n - 1] == index 1 (* 2) which gets evaluated and now
(specialArray, n - 1) * specialArray[n - 1] == index 2 (* 5)… popped off the stack…
until
(specialArray, n - 1) * specialArray[n - 1] == index 3(* 40)

Which I think resolves the final call and produces the proper output?
Did my attempted explanation makes any sense? : p

If I understand your explanation, that sounds about right. The only qualm I would have would be calling it a “call back”. I would define a callback as a function that is passed as an argument to a second function, to be used by that second function. But we are never passing a reference to a function here.

1 Like

No, the count is the same for humans or computers:

[1, 2, 3].length 
// 3

Humans and computers both agree that the count of that array is 3.

The issue is with indexes. Computer languages always (afaik) always 0-index. Humans often 1-index, but not always. For example in the US, the street level floor is 1, but in Europe, it is often 0. 24-hour clocks start with 0. Don’t think of it as human vs computer, think of it as 0-indexing vs 1-indexing, and realize that programming (afaik) deals with 0-indexing.

1 Like

Actually, I seem to remember that ForTran and COBOL use 1-based indexing. There are probably a few other scattered examples, but probably fewer as you get into more modern languages.

Glad you mentioned this.

so number of properties is 1 and up, but indexing is 0 and up?

1 Like