Recursion in Js

Question

Can someone please explain to me why we need (n-1) in the following code.

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

I understand that we have a base case of if (n <= 0){return 1} inorder for the code to not loop for ever but I dont understand the (n-1) and [n-1] in the recursive case of return multiply(arr, n - 1) * arr[n - 1]; .

Any help is much appreciated.

What else would you write there? Are you suggesting that passing n instead of n-1 would also work? — Bergi
– Bergi, Commented Oct 3, 2021 at 17:08
"I understand that we have a base case inorder for the code to not loop for ever" - well, could explain in your own words how this "looping" works, how you would reach that base case? — Bergi
– Bergi, Commented Oct 3, 2021 at 17:09

Michael Cleary · Accepted Answer · 2021-10-03 20:38:48Z

1

It looks like this function is meant to start with the last element of the array and recursively operate on each earlier element. This is why when calling the function recursively, you must pass in the next earlier element, i.e. n-1. This moves the function closer to the base case with each iteration.

edited Oct 3, 2021 at 20:38

answered Oct 3, 2021 at 16:54

Michael Cleary

1941 silver badge4 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

LightSolverCode Over a year ago

Thanks for your help, i understand it now

Marc Over a year ago

This can be much easier written with Array.prototype.reduce()

Stalinko · Accepted Answer · 2021-10-03 16:58:39Z

0

This function just multiplies all elements of the given array. Initially you must pass the array and it's length as n.

The last element for any array is n-1. Thus on the 1st iteration it will take the last element and multiply further until it reaches 0. Then it will stop.

Just try to run this function mentally in your head on some simple examples and you'll get it.

answered Oct 3, 2021 at 16:58

Stalinko

3,69434 silver badges38 bronze badges

1 Comment

LightSolverCode Over a year ago

Thanks for you help and advice i will do as you said

danh · Accepted Answer · 2021-10-03 17:21:56Z

0

The function could be improved, but you can understand it as-is by adding some debug logging...

function multiply(arr, n) {
  if (n <= 0) {
    return 1;
  } else {
    console.log(`recurse to multiply ${arr[n-1]} by elements in [${arr.slice(0,n-1)}]`);
    return multiply(arr, n - 1) * arr[n - 1];
  }
}

multiply([1, 2, 3], 3);

A clearer implementation wouldn't require the length param, and be clearer about decomposition...

// if the array has a first element, multiply it by the remainder of the array
function multiply(arr) {
  return arr.length ? arr[0] * multiply(arr.slice(1)) : 1;
}

console.log(multiply([1,2,3]))

edited Oct 3, 2021 at 17:21

answered Oct 3, 2021 at 17:08

danh

62.7k10 gold badges100 silver badges139 bronze badges

2 Comments

Bergi Over a year ago

Your "better implementation" has a time complexity of O(n²) however, in contrast to the linear complexity of the original function.

danh Over a year ago

Thanks, @Bergi. I considered that but figured it was more valuable for explaining recursion with the general form: "handle the first and recurse with the rest". Edited to say what I meant by "better".

Collectives™ on Stack Overflow

Recursion in Js

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related