使用递归查找数组中的最小数字？
int i = 0; int min = x[i]; while ( i < n ){ if ( x[i] < min ){ min = x[i]; } i++; } return min; 我编写了迭代表单来查找数组的最小数量。 但是我想编写一个带递归的函数。 请帮忙！
因为这听起来像家庭作业，这里有一个提示：数组中的最小值是第一个元素，或者是数组其余部分中的最小数字，以较小者为准。
单元素数组的最小数量是数组中的一个元素。
大小> 1的数组的最小数量是第一个元素的最小值和数组其余部分的最小值。
（未定义空数组的最小数量。）
这不是最佳解决方案，因为您可以将递归调用的结果保存在int变量中，但我不允许在练习中使用。
无论如何，这个函数使用递归搜索int数组中的最小值。 首先，它通过检查大小是否等于1来检查数组中有多少元素，然后返回第一个值作为结果。 如果表大于1（技术上也是低于），它会将数组中的最后一个值与数组其余部分的递归调用进行比较。
递归在0索引处停止，然后将该值与索引1进行比较。然后，它将索引0和1的最低值与索引3中的值进行比较，依此类推，直到达到最后一个值。
int minimum(int array[], int size) { if (size == 1) { return array[0]; } else { return (array[size] < minimum(array, size - 1)) ? array[size] : minimum(array, size - 1); } } int array[5] = {5, 99, 205, 1, 15}; int smallest = minimum(array, 4); // 4 = index of the last element
我的练习中的规则：
- 不要更改arrays
- 不要使用任何变量
- 使用递归
听起来像家庭作业，但你最好的选择是这样的：
int main(void) { int size = 2; int test[] = {0,1}; int min = test[0]; findMin(&min, test, size); printf("%d", min); } void findMin(int* min, int* test, int* length); void findMin(int* min, int* test, int* length) { if (length >= 0) { if (*test < *min) { *min = test; } findMin(min, test++, (*length)--); } }
这是一个返回指向最小值的指针的函数：
#include int *recursiveMin(int *x, int n) { if (x == NULL || n == 0) return NULL; if (n == 1) return x; int *t = recursiveMin(x + 1, n - 1); return *x < *t ? x : t; }
一般的递归规则是避免“小步骤” – 所以“第一个元素与数组的其余部分相比”是非常糟糕的主意。 尝试将数组处理成两半，如下所示：
min( array ) { if size of array == 1 return array[0] else if size of array == 2 return array[0] < array[1] ? array[0] : array[1] else { firstmin = min( firsthalf) // stored to avoid double calls secondmin = min( secondhalf) firstmin < second_min ? firstmin : secondmin } }
进一步优化：
- 避免数组副本 - 考虑使用类似quicksort的签名（数组，from，to）
- 避免大小<2的递归调用
你为什么要用递归来做这个？ 递归的一般规则是，如果可以在简单的线性循环中执行，则不要使用递归。
尝试：
int recursive_min(list arr) { return recursive_min(arr); }
虽然这在命令式语言中不起作用。
一个更严肃的答案是伪代码：
func recursive_min( list l ) { head = l[1] tail = l[2<->end] if l.length==1 return head else return min(head,recursive_min(tail)) }
虽然如果l为空则不起作用。
int findMin(int a[], int len) { // normal version // if (len==1) return a[0]; // return (a[len-1] < findMin(a,len-1))? a[len-1] : findMin(a,len-1); // memoization version, sort of? int rightside; if (len==1) return a[0]; rightside = findMin(a,len-1); return (a[len-1] < rightside)? a[len-1] : rightside; }
#include #include using namespace std; int min(int [], int); void mostrar(int [], int); int main() { int f[] = {4, 9, 0, -1, 5, 8, -3, 6, -4, 0}; int t = sizeof(f)/sizeof(int); cout << "\nEl valor m\xa1nimo para los valores:\n"; mostrar(f, t); cout << "\nes: " << min(f, t); system("pause>nul"); } int min(int x[], int p) { if (p == 1) return x[0]; int aux = min(x+1, p-1); return x[0] < aux ? x[0] : aux; } void mostrar(int v[], int k) { if (k > 1) mostrar(v, k-1); cout << v[k-1] << " "; }
const int = 20; int getmin (int v[], int n); main () { int v[N]; int i,n,min; printf("\n\tType number of elements:\t"); scanf("%d",&n); for (i=0;i0) { if ( v[n-2] > v[n-1] ) { v[n-2]=v[n-1]; } getmin (v,n-1); } return v[n-2]; }