再帰に関する質問がたくさんありますが、配列要素の合計などの単純な再帰アルゴリズムを基本的に理解しています。しかし、私の友人は、配列を逆にする次のコードを教えてくれました。
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 ループを使用して配列を逆にする方法を知っています。しかし、このコードは再帰について私を本当に混乱させました。
上記のコード行を説明できる人はいますか?
に等しい
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) は、再帰停止 (オリジナルでは間違っていた) と同等です。
このアルゴリズムの背後にある考え方は、各ステップにあります。
-: 配列の最後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]の th 要素のアドレスであることに注意してください。n+1をお持ちint *b = &a[1]の場合はb[0] == a[1]、b[1] == a[2]、 などです。
そう：
&a[1]は、 array の 2 番目の要素から始まる配列を参照しaます。s - 2再帰的に渡す配列の長さが 2 要素分短いことを意味します。array がある場合[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。
簡略化されたクレイジー ウォーク トラフ。
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} )そして、次のようなもの
#::::::::::::::::::::::::::::::::::::::::::::::::::::
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.
関数は次のように呼び出す必要があります。
最初の 'if' は、配列に少なくとも 2 つの要素があることを確認します。次に、関数が行うことは、配列の最初と最後の要素の位置を交換することです。
再帰呼び出しは、次のステップが機能しなければならない境界を変更します。配列の先頭の位置を 1 つ増やし、配列の末尾の位置を 1 つ減らします。これらの 2 つの要素は、この反復で逆になっているためです。
認識すべき重要なことは、aは配列の最初の要素へのポインターであるためa、 と同じ&a[0]です。&a[1]配列の 2 番目の要素へのポインタです。したがって、関数を&a[1]引数として呼び出すと、2 番目の要素で始まる部分配列に対して機能します。
&a[1]つまりa + 1、配列の 2 番目の要素へのポインタです。関数呼び出しは、配列の「中間」s-2要素を逆にします。