這個遞歸C代碼是如何工作的？

Question

有很多遞歸問題，我基本上理解一些簡單的遞歸算法，如數組元素的總和。然而，我的朋友給了我這個代碼反轉的數組：

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] 
} 

我知道如何使用正常的循環扭轉數組。但是這段代碼讓我很困惑遞歸。

任何人都可以解釋上面的代碼行嗎？

Answer 1

它等同放着清單

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）相當於遞歸限制器（原來是錯誤的）。

Answer 2

要認識到的重要一點是a是指向數組的第一個元素的指針，因此a與&a[0]相同。 &a[1]是指向數組的第二個元素的指針。因此，如果您以&a[1]作爲參數調用該函數，則它適用於以第二個元素開頭的子數組。

Answer 3

&a[1]相當於a + 1，即指向數組的第二個元素的指針。函數調用反轉陣列的「中間」s-2元素。

Answer 4

該函數具有與被調用：

• 的指針數組的第一個元素。在C中，可以使用數組的名稱來引用它。
• 數組的大小。

第一個'if'檢查數組是否至少有兩個元素。接下來，函數做的是交換數組的第一個元素和最後一個元素的位置。

遞歸調用改變了下一步必須工作的邊界。它將數組的起始位置增加一個位置，並將數組的末尾減少一個位置;因爲在這次迭代中這兩個要素已經被逆轉了。

Answer 5

該算法背後的想法是在每個步驟：

- ：交換所述陣列的最後一個a[s-1]和第一a[0]元素：

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

- ：和以遞歸方式交換的中間位置：

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

要理解語法，請記住&a[n]是n+1 th elemen的地址t給定數組。如果你有int *b = &a[1]，那麼b[0] == a[1],b[1] == a[2]等

所以：

• &a[1]指起始於陣列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) 

很酷的事情是，這種分析告訴我們，終止condtion s <= 2是錯誤的：在最裏面的2種元素偶數大小的數組永遠不會交換。它應該更改爲s < 2。

Answer 6

Simplified Crazy walk trough;

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 */ 
} 

---

由於字符數組"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被推到
• 7被推到堆棧
• 返回地址呼叫者被壓入堆棧
• 等堆棧（A {BCDEFG}）
• 函數稱爲

而且像

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

reverse(ABCDEFG, 7); # Push to STACK 0xB (As List 1) 
#==================================================== 
789abcd <- Memory address. 
ABCDEFG <- Values. 
<- 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 
<- 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. 
<- 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. 
<- 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.