c - 在 C 中递归解决问题

Question

我们的教授给了我们以下作业:

A "correct" series is one in which the sum of its members equals to the index of its first member.

该程序应该在 n 个数列中找到最长的“正确”数列的长度。

例如:如果输入序列是 arr[4]={1, 1, 0, 0}输出(最长的“正确”系列)将是 3。
arr[0]=1。 0!=1 因此这里最长的系列是 0。
arr[1]=1,and 1=1. 但以下成员的总和也为 1，如下所示:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0，因此这里最长的级数是3。

此示例中的输出是 3。

这是我目前所拥有的:

int solve(int arr[], int index, int length,int sum_so_far)
{
     int maxwith,maxwithout;

     if(index==length)
         return 0;

     maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]);
     maxwithout = solve(arr,index+1,length,arr[index+1]);

     if(sum_so_far+arr[index]==index)
         if(maxwith>maxwithout) 
            return maxwith;

     return maxwithout;

     return 0;
}



int longestIndex(int arr[], int index,int length)
{
     return solve(arr,0,length,0);
}

我在这里做错了什么？

我们不应该在这个分配上循环。

Answer 1

嗯，这个程序有几个问题。

最明显的是，“返回 maxwithout；返回 0；”应该给出一个编译错误:没有办法到达最后一个 return 语句。

其次，您递归求解“maxwith”路径，直到到达数组末尾。然后你将递归到 maxwithout，第一次用 index=4 命中它。我认为这行不通。

坦率地说，我不认为这个问题真的需要递归。最自然的解决方案是嵌套循环:

for (int start=0;start<length;++start)
{
  for (int end=start;end<length;++end)
  {
    // calculate the sum of arr[start]->arr[end] and compare to start
  }
}

或者类似的东西。

问题是否需要通过递归来解决，或者这只是您的第一个好的解决方案？

编辑

好的，所以你必须使用递归。我想这节课的重点是学习使用递归，而不一定是以最自然或最有效的方式解决问题。 (我个人认为老师应该想出一个问题，递归是一个自然的解决方案，但我想我们今天不是来批评老师的。)

我不想给你做功课，但我会给你一个提示。您可以使用递归来模拟循环，方法是将中断条件放在函数的开头，并将递归调用放在带有 +1 参数的函数的末尾。也就是说，而不是写

for (int x=0;x<10;++x) { ... whatever ...}

你可以写

void forx(int x)
{
  if (x>=10)
    return;
  ... whatever ...
  forx(x+1);
}

所以在这种情况下，我会做类似的事情:

void endloop(int start, int end)
{
  if (end>=arrayLength)
    return;
  ... work on running total ...
  endloop(start, end+1);
}

void startloop(int start)
{
  if (start>=arrayLength)
    return;
  endloop(start, start);
}
int main()
{
  ... setup ...
  startloop(0);
  ... output ...
}

参数列表不一定完整。正如我所说，我不想为你做功课，只是给你一个开始的提示。