时间戳

首页 > 解决方案 > 以下问题中的递归如何工作？

arrays - 以下问题中的递归如何工作？

问题描述

我有一个问题和一个测试的解决方案。

问题是：编写一个函数，如果我们可以将一个数组分成两个不同的组，它们的总和相等，则返回 1，否则返回 0。例如：数组：[1,4,0​​,3] 可以分为 2总和相等的组，因此：1+3=0+4

建议的解决方案写在下面：

#include<stdio.h>

int can_split(int arr[], int n, int sum1, int sum2); // Function Signature

int can_split(int arr[], int n, int sum1, int sum2)
{
    if (n == 0)
        return sum1 == sum2;
    return can_split(arr + 1, n - 1, sum1 + arr[0], sum2) || can_split(arr + 1, n - 1, sum1, sum2 + arr[0]);
}

int main()
{
    int sum1_main = 0, sum2_main = 0;
    int arr_main[] = { 1,2,4 };
    printf("Function returned: %d", can_split(arr_main, 4, sum1_main, sum2_main));
    return 0;
}

我不明白的是这条线的想法：

return can_split(arr + 1, n - 1, sum1 + arr[0], sum2) || can_split(arr + 1, n - 1, sum1, sum2 + arr[0]);

当涉及到复杂的问题时，递归对我来说是一个非常困难的话题。

如果有人能解释这条线是如何工作的以及老师为什么要写 || 将非常感激 ? 我知道它的意思是“或”，但它在这里到底做了什么？

标签： arrayscxcoderecursionnumbers

解决方案

当涉及到复杂的问题时，递归对我来说是一个非常困难的话题。

递归并不是一个很难的话题，而是一种思考和查看代码的方式（不仅仅是代码）。这主要是一个习惯和实践的问题，你越会阅读、写作和思考递归，它对你来说就越自然。
我要补充一点，恕我直言，在软件开发或计算机科学方面，这是一个不可避免且必须掌握的概念。

关于这一行：

return can_split(arr + 1, n - 1, sum1 + arr[0], sum2) || can_split(arr + 1, n - 1, sum1, sum2 + arr[0]);

变量的含义如下：

  • arr表示我们正在考虑的数组的当前元素的地址。在递归调用的每一步，我们都会考虑下一个元素（因此arr + 1which 指向数组中的下一个元素）
  • n表示要考虑的元素数量：我们开始第一次调用n = 4表示数组长度的函数。我们n用作停止条件。当 时n == 0，我们知道所有元素都已被考虑。
  • sum1并sum2表示当前的总和值

现在，line 的含义如下：
“当且仅当
-> 数组可以与第一组中的当前元素
或（因此||)
-> 数组可以分成两组相等的和与第二组中的当前元素。"

我们对每个元素都这样做，这保证了我们最终会得到正确的结果。

通常，理解代码的一个好方法是在一个小示例上手动运行它（这里将是 arr_main {1, 3, 0, 4}）。
这是它的开始方式：

can_split(arr_main, 4, 0, 0)  // no element has been affected to any sum
n == 0 ? no so we continue
return can_split(arr + 1, 3, 1, 0)   // the value 1 is affected to sum1
             || 
       can_split(arr + 1, 3, 0, 1);  // the value 1 is affected to sum2

一直如此，直到所有值都受到影响。

推荐阅读