如何使用递归函数找到的最大数量

Question

我想了解如何找到使用递归函数的最大数，但我真的不知道怎么样。有了这个代码：

#include <stdio.h>
#include <stdlib.h>
int main()
{

    int ar[100],n,i;
    int *ptr;
    printf("Enter size of the list:");
    scanf("%d", &n);
    printf("Printing the list:\n");
    for (i = 0; i < n ; i++)
    {
        scanf("%d", &ar[i]);
    }
    ptr=&ar;
    int max=maximum(ptr,n);
    printf("ma %d",max);
    return 0;
}
int maximum(int ar[], int n)
{

    int max;
    if(n+1==1)
    {
        return ar[n];
    }
    max =maximum(ar,n-1);
    return ar[n]>max?ar[n]:max;
}

什么是它实际上做，以及如何？难道是正确使用指针指向整数数组？我希望你能帮助我理解了！

Answer 1

您预留的内存为100个整数数组与int ar[100]，并且您输入这是使用n设置scanf("%d", &n)。如果在此阶段输入一个大于100，你的程序将赛格的错，因为你的循环for (i = 0; i < n ; i++)将试图访问ar[100]这是一个内存访问错误（最高数组索引可以是ar[100 - 1]，发现100 - 1 <100）。不管怎么说，你填写循环n的ar指数。 ptr = &ar刚分配到ar的ptr起始地址。通过ptr = ar也可以工作的方式，&是没有必要的。现在你可以使用你ptr使用ar以同样的方式。

了解递归最简单的方法是直来直去maximum的最后一次通话。但首先，要明白你传递ptr到这是与传递ar功能（请记住，他们是同样的事情在main自ptr = ar）。

所以在最后调用maximum，当n + 1 == 1（同n == 0），它返回ar[n]这是ar[0]，这是第一次你'Printing the list'进入（这是存储在ar[0]）的数量。

现在，在倒数第二个呼叫maximum，n + 1 == 1是假的，因为n = 1所以我们去max = maximum(ar, n - 1)。这是最后一次通话的结果maximum我刚才解释，所以max具有ar[0]的价值。现在你有return ar[n] > max ? ar[n] : max，这是一样的return ar[1] > ar[0] ? ar[1] : ar[0]。这是一样的

if (ar[1] > ar[0]) {
  return ar[1];
} else {
  return ar[0];
}

你可以看到，这个返回取其大，ar[0]或ar[1]。现在的倒数第三呼叫maximum，max是倒数第二个呼叫maximum的结果。你可以看到的模式出现。您将返回取较大者：max或ar[n]的通话其余所有的人maximum，和你到了第一次调用maximum的时候，你会相比ar所有值找到它的最大并返回。

此外，什么阿贾伊说的很对，ar[n]正在访问你永远在循环初始化的值。你应该在int max = maximum(ptr, n - 1)写main来解决这个问题。

Answer 2

我与尾递归的解决方案：

int maximum(int a[], int n)
{
    if (n == 1)
        return a[0];
    --n;
    return maximum(a + (a[0] < a[n]), n);
}

Demo on compiler explorer

Answer 3

要了解如何maximum作品，只是试图找到在maximum功能不变的一些

int maximum(int ar[], int n)
{
    int max;
    if(n==0)
    {
        return ar[n];
    }
    max =maximum(ar,n-1);
    /* at this point MAX keeps the maximum of the subarray [0..N-1] and using this 
       we try to get by induction the maximum of [1..N]. */
    return ar[n]>max?ar[n]:max;
}

Answer 4

考虑到定义：

#include <stdio.h>
#include <stdlib.h>

void maximum(int nums[], int size, int index, int * max)
{
  if (index != size) {
    if (nums[index] > *max)
      *max = nums[index];
    maximum(nums, size, ++index, max);
  }
}

int main()
{
  int * nums;
  int size, i, max;

  fprintf(stderr, "Enter size of the list: "); /* stderr to flush without \n */
  if ((scanf("%d", &size) != 1) || (size <= 0)) {
    puts("wrong size");
    return 0;
  }

  if ((nums = malloc(size * sizeof(int))) == 0) {
    puts("cannot allocate nums");
    return 0;
  }

  for (i = 0; i != size; ++i) {
    if (scanf("%d", &nums[i]) != 1) {
      puts("invalid number");
      return 0;
    }
  }

  max = nums[0];
  maximum(nums, size, 1, &max);
  free(nums);
  printf("max = %d\n", max);

  return 0;
}

执行：

% gcc -O2 -pedantic -Wall m.c
% ./a.out
Enter size of the list: 3
3
1
2
max = 3

最大是递归的，但是这是一个终端递归，所以编译器可以将其移除，以产生循环。所以，最大的似乎你要求的，但堆栈不会有大量甚至爆炸是递归的：

% ( echo 100000000 ; yes 1 ) | ./a.out
Enter size of the list: max = 1

如果我删除选项-O2的生成代码使用递归和堆栈爆炸：

% gcc -pedantic -Wall m.c
% ( echo 100000000 ; yes 1 ) | ./a.out
Enter size of the list: Segmentation fault