Блог

Пожалуйста, помогите мне понять, как следующий код всегда возвращает наименьшее значение в массиве. Я попытался переместить позицию 3, но ей всегда удается вернуть ее, независимо от ее положения в массиве.

 let myA = [12,3,8,5] let myN = 4  function F4(A,N) {  if(N==1){  return A[0]  }  if(F4(A,N-1) lt; A[N-1]){  return F4(A,N-1)  }  return A[N-1] }  console.log(F4(myA,myN))  

Это довольно сложно понять интуитивно. Также очень важно, чтобы вы изучили процесс решения такого рода проблем, а не просто получили ответ.

Если мы сначала рассмотрим код с несколькими комментариями и именованными переменными, он выглядит так:

 let myA = [12,3,8,5]; let myN = myA.length;  function F4(A, N) {  // if (once) there is only one element in the array "A", then it must be the minimum, do not recurse  if (N === 1){  return A[0]  }   const valueFromArrayLessLastEl = F4(A,N-1); // Goes 'into' array  const valueOfLastElement = A[N-1];   console.log(valueFromArrayLessLastEl, valueOfLastElement);    // note that the recursion happens before min(a, b) is evaluated so array is evaluated from the start  if (valueFromArrayLessLastEl lt; valueOfLastElement) {  return valueFromArrayLessLastEl;  }   return valueOfLastElement; }  console.log(F4(myA, myN))  

и производит

 12 3 // recursed all the way down 3 8 // stepping back up with result from most inner/lowest recursion 3 5 3  

но для того, чтобы получить представление, жизненно важно, чтобы вы подошли к проблеме, рассмотрев простейшие случаи, и расширили оттуда. Что произойдет, если мы напишем код для случаев N = 1 и N = 2 :

 // trivially take N=1 function F1(A) {  return A[0]; }  // take N=2 function F2(A) {  const f1Val = F1(A); // N-1 = 1  const lastVal = A[1];   // return the minimum of the first element and the 2nd or last element  if (f1Val lt; lastVal) {  return f1Val;  }   return lastVal; }  

Пожалуйста, обратите внимание, что массив не изменяется, я говорю так, как будто это происходит потому, что значение N уменьшается при каждой рекурсии.

С myA = [12, 3, 8, 5] F1 всегда будет возвращать 12. F2 будет сравнивать это значение 12 с 3, значением n-го элемента-1, и возвращать минимальное значение.

Если вы сможете опираться на это, чтобы понять, что F3 будет делать, тогда вы сможете экстраполировать оттуда.

Поиграйте с этим, переупорядочивая значения myA , но главное, посмотрите на результат, когда вы увеличите N с 1 до 4.

В качестве примечания: переместив рекурсивный вызов F4(A,N-1) на локальную константу, я предотвратил его повторный вызов с одинаковыми значениями.