0

有很多递归问题，我基本上了解一些简单的递归算法，例如数组元素的总和。但是，我的朋友给了我这个反转数组的代码：

void r(int a[], int s)
{
     if(s <=2 ) return;
     int t = a[0];
     a[0] = a[s-1];
     a[s-1] = t;

     r(&a[1], s-2); //  this line confused me, why &a[1]
}

我知道如何使用普通的 for 循环来反转数组。但是这段代码真的让我对递归感到困惑。

任何人都可以解释上面的代码行吗？

4

6 回答 6

3

它相当于

void r(int *arr, size_t len)
{
     for ( ; len >= 2; arr+=1,len-=2 ) {
       int t = arr[0];
       arr[0] = arr[len-1];
       arr[len-1] = t;
       }

}

，其中递归调用被循环替换。循环（arr+=1,len-=2）的“增量”部分与递归调用的参数完全相同；结束条件 ( len >= 2) 等价于递归停止器（原来是错误的）。

于 2012-04-15T14:59:55.323 回答
1

这个算法背后的想法是在每一步：

-：交换数组的最后一个元素a[s-1]和第一个元素：a[0]

    int t = a[0];
    a[0] = a[s-1];
    a[s-1] = t;

-: 并递归交换中间：

    r(&a[1], s-2);

要理解语法，请记住这是给定数组的第 th 个元素的&a[n]地址。n+1如果你有int *b = &a[1]，那么b[0] == a[1]，，b[1] == a[2]等等。

所以：

  • &a[1]指从 array 的第二个元素开始的数组a。
  • s - 2意味着您递归传递的数组的长度短了 2 个元素。

如果你有一个数组[1 2 3 4 5 6 7 8 9 10]，递归进行时会发生以下情况：

[1 2 3 4 5 6 7 8 9 10] // r(&a[0], 10)
10 [2 3 4 5 6 7 8 9] 1 //   r(&a[1], 8
10 9 [3 4 5 6 7 8] 2 1 //     r(&(&a[1])[1], 6)
10 9 8 [4 5 6 7] 3 2 1 //       r(&(&(&a[1])[1])[1], 4)
10 9 8 7 [5 6] 4 3 2 1 //         r(&(&(&(&a[1])[1])[1])[1], 2)

很酷的是，这个分析告诉我们终止条件s <= 2是错误的：偶数数组中最里面的 2 个元素永远不会被交换。应改为s < 2.

于 2012-04-15T15:25:08.557 回答
1

简化的疯狂步行槽；

void reverse(int a[], int s)
{
    int temp;              /* temporary value */

    if (s <= 2) return;    /* trigger done */

    t        = a[0];       /* temp = first index of a */
    a[0]     = a[s - 1];   /* a[0] = a[end - 1] (end including \0) */
    a[s - 1] = t;          /* a[end - 1] = temp */

    r(&a[1], s - 2);       /* pass address of a[1] and end - 2 */
}

给定 char 数组"ABCDEFG"

简化的内存表可以是：

Address  Value
      7      A
      8      B
      9      C
      a      D
      b      E
      c      F
      d      G

/* Or as used here: */

789abcd <- Simplified memory address
ABCDEFG

我们得到；main()来电reverse(ABCDEFG, 7)

清单 1

  • 地址参考。被A压入堆栈 (A{BCDEFG})
  • 7 被压入堆栈
  • 调用者的返回地址被压入堆栈
  • 等等
  • 函数调用

和类似的东西

#::::::::::::::::::::::::::::::::::::::::::::::::::::

reverse(ABCDEFG, 7); # Push to STACK 0xB (As List 1)
#====================================================
789abcd <- Memory address.
ABCDEFG <- Values.
0123456 <- Indexes for a in recursion 1.

if (7 <= 2) return;
temp = A
               +     .
a[0] = a[6] => ABCDEFG = GBCDEFG
                     +
a[6] = temp => GBCDEFG = GBCDEFA

reverse(BCDEFA, 5); # Push to STACK 0xC (As in List 1)
#====================================================
 7 89abcd <- Memory addresses.
[G]BCDEFA <- Values
   012345 <- Indexes for a in recursion 2.

if (5 <= 2) return;
temp = B
               +   .
a[0] = a[4] => BCDEFA = FCDEFA
                   +
a[4] = temp => FCDEFA = FCDEBA

reverse(CDEBA, 3); # Push to STACK 0xD (As in List 1)
#====================================================
 78 9abcd <- Memory addresses.
[GF]CDEBA <- Values.
    01234 <- indexes for a in recursion 3.

if (3 <= 2) return;
temp = C
               + .
a[0] = a[2] => CDEBA = EDEBA
                 +
a[2] = temp => EDEBA = EDCBA

reverse(DCBA, 1); # Push to STACK 0xE (As in List 1)
#====================================================
 789 abcd <- Memory addresses.
[GFE]DCBA <- Values.
     0123 <- Indexes for a in recursion 4.
if (1 <= 2) return; YES!

#:::: roll back stack ::::

Pop STACK 0xE
Pop STACK 0xD
Pop STACK 0xC
Pop STACK 0xB
We are back in main() and memory region 789abcd has 
been altered from ABCDEFG to GFEDCBA.
于 2012-04-15T16:02:24.250 回答
0

要实现的重要一点是，它a是指向数组第一个元素的指针，因此a与&a[0]. &a[1]是指向数组第二个元素的指针。因此，如果您使用&a[1]作为参数调用该函数，它将在以第二个元素开头的子数组上工作。

于 2012-04-15T14:43:14.857 回答
0

&a[1]等价于a + 1，即指向数组第二个元素的指针。函数调用反转数组的“中间”s-2元素。

于 2012-04-15T14:43:20.733 回答
0

该函数必须通过以下方式调用：

  • 指向数组第一个元素的指针。在 C 中，它可以通过使用数组的名称来引用。
  • 数组的大小。

第一个“if”检查数组是否至少有两个元素。接下来，该函数所做的是交换数组的第一个和最后一个元素的位置。

递归调用改变了下一步必须工作的界限。它将数组的开头增加一个位置，并将数组的结尾减少一个位置；因为这两个元素在本次迭代中被颠倒了。

于 2012-04-15T15:11:54.803 回答