設計一個找到陣列最小值的遞回演算法

我在考慮遞回演算法（這是一個理論問題，所以編程語言并不重要）。它包括找到一組數字的最小值

我是這樣想的：讓“n”成為集合中元素的數量。讓我們將集合重新排列為：

• (a, (b, c, ..., z))。

函式從左到右移動，第一個元素在第一階段被假定為最小值（當然，它是第 0 個元素，a）。接下來的步驟定義如下：

• (a, min(b, c, ..., z) )，檢查 a 是否仍然是最小值，或者如果假設 b 為最小值，則 (a or b, min(c, d, ..., z) )，另一個檢查條件，(a or b or c, min(d, e, ..., z))，檢查條件等。

我認為理論上的偽代碼可能如下：

f(x) {

// base case 
if I've reached the last element, assume it's a possible minimum, and check if y < z. then return a value to stop recursive calls.  
// inductive steps
if ( f(i-th element) < f(i 1, next element) ) { 
/* just assume the current element is the current minimum */ 
} 
} 

我在基本情況下遇到問題。我不知道如何正式化它。我想我已經理解了它的基本思想：基本上就是我用偽代碼寫的，對吧？

到目前為止我寫的有意義嗎？對不起，如果不清楚，但我是初學者，我是第一次學習遞回，我個人覺得它很混亂。所以，我已經盡力解釋了。如果不清楚，請告訴我，我會嘗試用不同的詞更好地解釋它。

uj5u.com熱心網友回復：

遞回問題很難想象。讓我們舉個例子：arr = [3,5,1,6]

這是一個相對較小的陣列，但仍然不容易想象遞回將如何從頭到尾作業。

提示：嘗試減小輸入的大小。這將使可視化變得容易，并幫助您找到base case. 首先決定我們的函式應該做什么。在我們的例子中，它從陣列中找到最小的數字。如果我們的函式適用于大小陣列，n那么它也應該適用于大小陣列n-1（信仰的遞回跳躍）。現在使用這個我們可以減少輸入的大小，直到我們不能進一步減少它，這應該給我們我們的基本情況。

讓我們使用上面的例子：arr = [3,5,1,6]

讓我們創建一個函式findMin(arr, start)，它接受一個陣列和一個起始索引，并回傳從起始索引到陣列末尾的最小數字。

1st Iteration : [3,5,1,6]
// arr[start] = 3, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [5,1,6]

2nd Iteration : [5,1,6]
// arr[start] = 5, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [1,6]

3rd Iteration : [1,6]
// arr[start] = 1, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [6]

4th Iteration : [6]
// arr[start] = 6, Since it is the only element in the array, it is the minimum.
// This is our base case as we cannot reduce the input any further.
// We will simply return 6.

------------ Tracking Back ------------

3rd Iteration : [1,6]
// 1 will be compared with whatever the 4th Iteration returned (6 in this case).
// This iteration will return minimum(1, 4th Iteration) => minimum(1,6) => 1 

2nd Iteration : [5,1,6]
// 5 will be compared with whatever the 3th Iteration returned (1 in this case).
// This iteration will return minimum(5, 3rd Iteration) => minimum(5,1) => 1 

1st Iteration : [3,5,1,6]
// 3 will be compared with whatever the 2nd Iteration returned (1 in this case).
// This iteration will return minimum(3, 2nd Iteration) => minimum(3,1) => 1 

Final answer = 1

function findMin(arr, start) {
  if (start === arr.length - 1) return arr[start];
  return Math.min(arr[start], findMin(arr, start   1));
}

const arr = [3, 5, 1, 6];
const min = findMin(arr, 0);
console.log('Minimum element = ', min);

這是初學者練習遞回的好問題。您也可以嘗試這些問題進行練習。

1. 使用遞回反轉字串。
2. 使用遞回反轉堆疊。
3. 使用遞回對堆疊進行排序。

uj5u.com熱心網友回復：

對我來說，更像是這樣：

int f(int[] x)
{
    var minimum = head of X;
    if (x has tail)
    {
        var remainder = f(tail of x);
        if (remainder < minimum)
        {
            minimum = remainder;
        }
    }
    return minimum;
}

uj5u.com熱心網友回復：

你有正確的想法。

你已經正確地觀察到了

min_recursive(array) = min(array[0], min_recursive(array[1:]))

該函式不關心誰在呼叫它或在它之外發生了什么——它只需要回傳傳入陣列的最小值。基本情況是陣列具有單個值。該值是陣列的最小值，因此它應該只回傳它。否則，通過再次呼叫自身來找到陣列其余部分的最小值，并將結果與??陣列的頭部進行比較。

其他答案顯示了一些編碼示例。

uj5u.com熱心網友回復：

這是您提出的問題的遞回解決方案，使用 JavaScript：

a = [5,12,3,5,34,12]

const min = a => {
  if (!a.length) { return 0 }
    if (a.length === 1) { return a[0] }
    return Math.min(a[0], min(a.slice(1)))
}

min(a)

請注意首先檢測最簡單的情況（空陣列），然后是更復雜的情況（單元素陣列），最后是遞回呼叫，這會將更復雜的情況簡化為更簡單的函式。

但是，您不需要遞回來遍歷一維陣列。

標籤：算法 递归

上一篇：JS中陣列的等邊

下一篇：Python__repr__方法：撰寫JS等價物？