无法理解递归

Question

int fun(int a[],int n)
{
int x;
if(n == 1)
return a[0];
else
x = fun(a, n - 1);
if(x > a[n - 1])
return x;
else
return a[n - 1];
}

我无法理解这种递归的功能。如果有人能举例说明的话。

Answer 1

这是以下递归关系

• 大小为1的数组中最大的元素是第一个(也是最后一个！(元素
• 大小>1是中的较大者
  • 子数组中最大的元素，不包括最后一个元素
  • 最后一个元素

Answer 2

这里有一个非常具体的例子。

假设我们有一个数组int v[] = {1,3,2}，然后看看fun(v, 3)。

在函数体中替换这些值，就会得到

int x;
if(3 == 1)
return v[0];
else
x = fun(v, 3 - 1);  —> Can't continue without this value
if(x > v[3 - 1])
return x;
else
return v[3 - 1];

第一个条件为false，因此我们需要确定fun(v, 2)。

再次替换，这是

int x;
if(2 == 1)
return v[0];
else
x = fun(v, 2 - 1); —> Can't continue without this value
if(x > v[2 - 1])
return x;
else
return v[2 - 1];

第一个条件仍然为false，因此我们需要确定fun(v, 1)。

这是

int x;
if(1 == 1)
return v[0];
else
x = fun(v, 1 - 1);
if(x > v[1 - 1])
return x;
else
return v[1 - 1];

现在第一个条件为true，所以我们返回v[0]，即1，并继续使用中断的fun(v, 2):

int x;
if(2 == 1)
return v[0];
else
x = 1;  <— continue here
if(x > v[2 - 1])
return x;
else
return v[2 - 1];

现在，x > v[1]显然是false，所以我们将v[1](即3(返回给fun(v, 3):

int x;
if(3 == 1)
return v[0];
else
x = 3;    <— continue here
if(x > v[3 - 1])
return x;
else
return v[3 - 1];

由于3 > v[2]，我们返回3。

相同功能的一个较短变体是

int fun(int a[], int n)
{
return n == 1 ? a[0] : max(a[n-1], fun(a, n-1));
}