誰かが次のコードで再帰を理解するのを助けることができますか？

Question

私は再帰の初心者です。次のコードで再帰がどのように機能するかを誰かに教えてもらえますか？どんな助けもありがとう。

int f(int *p, int n) 
{ 
    if (n <= 1) return 0; 
    else return max(f(p+1,n-1),p[0]-p[1]); 
} 
int main() 
{ 
    int a[] = {3,5,2,6,4}; 
    printf("%d", f(a,5)); 
} 

具体的には、私はこの行で行われている再帰を理解していないです：

max(f(p+1,n-1),p[0]-p[1]) 

Answer 1

機能fが配列し、その配列のサイズを取得し、再帰的に近隣​​の値を比較し、最終的に戻って隣接する値間の最大距離（数値、非絶対）。あなたの場合、関数は3を返します。これは、5と2の間の最大距離3を表します。この場合の2と6の差は、絶対値がとられていないので、-4です。

f(p+1,n-1)には2種類の演算があるため、再帰的なケースは少し混乱します。 p+1はポインタの演算であり、n-1は通常の数値演算です。 p+1は配列ポインタを次の要素に進めているだけで、n-1は配列サイズをデクリメントしているため、比較する要素がなくなったときに関数が終了します。

ベースケースでは、すべてのペアを既にチェックしている場合、最高距離はゼロであると言われています。

計装コード

次のコードは、max()使用を除去し、最大の差を計算するための単純な三元表現を選ぶなど、インストルメントされます。機能的には、これは投稿されたものと同じでなければなりませんが、機能にはprintfと、アドレスにはmain()が追加されています。それは上記のことを増幅するはずです。

#include <stdio.h> 

int f(int *p, int n) 
{ 
    // no sense in checking zero or one element. 
    if (n <= 1) 
     return 0; // actually, this should be INT_MIN, but whatever 

    // print this call-frame for the values we're interested in 
    printf("p = %p, n = %d, p[0] = %d, p[1] = %d\n", 
      (const void*)p, n, p[0], p[1]); 


    int lhs = f(p+1,n-1); // recurse here 
    int rhs = p[0] - p[1]; 

    // return the maximum of the two values 
    return (lhs < rhs) ? rhs : lhs; 
} 

int main() 
{ 
    int a[] = {3,5,2,6,4}; 
    printf("%p %d", (const void*)a, f(a,5)); 
} 

出力（注：アドレスは、システムによって異なります）最後の行は、main()でa[]のベースアドレスを示すこと

p = 0x7fff5fbff970, n = 5, p[0] = 3, p[1] = 5 
p = 0x7fff5fbff974, n = 4, p[0] = 5, p[1] = 2 
p = 0x7fff5fbff978, n = 3, p[0] = 2, p[1] = 6 
p = 0x7fff5fbff97c, n = 2, p[0] = 6, p[1] = 4 
0x7fff5fbff970 3 

注意。関数の最初の呼び出し（上の行）は、同じアドレスを示しています。先に説明したポインタの算術に基づいてアドレスがどのように調整されるかに注意してください。 nの値の減少と相まって、それぞれの再帰呼び出しは「より短い」シーケンスになります。実際には同じシーケンスです。異なる位置から開始し、異なる要素数で開始します。

これだけです。

Answer 2

私達ができると我々は多くのシンプルなラインに機能を分割場合、物事を見ることが容易になるとprintf年代をデバッグ追加する可能性があります。ここでは

#include <stdio.h> 

int a[] = { 3, 5, 2, 6, 4 }; 
int level; 

#define debug(_fmt...) \ 
    do { \ 
     for (int lvl = level << 1; lvl > 0; --lvl) \ 
      fputc(' ',stdout); \ 
     printf(_fmt); \ 
    } while (0) 

static inline int 
max(int x,int y) 
{ 
    int ret; 

    ret = (x > y) ? x : y; 

    return ret; 
} 

int 
f(int *p, int n) 
{ 
    int pp; 
    int val; 
    int ret; 

    debug("f: ENTER p=%p(%ld) n=%d level=%d\n",p,p - a,n,level); 

    if (n <= 1) 
     ret = 0; 
    else { 
     ++level; 
     val = f(p + 1,n - 1); 
     --level; 

     pp = p[0] - p[1]; 
     debug("f: SUBVAL val=%d pp=%d\n",val,pp); 
     ret = max(val,pp); 
    } 

    debug("f: EXIT ret=%d level=%d\n",ret,level); 

    return ret; 
} 

int 
main(void) 
{ 
    printf("RESULT: %d\n", f(a, 5)); 
} 

が出力されます。

f: ENTER p=0x601050(0) n=5 level=0 
    f: ENTER p=0x601054(1) n=4 level=1 
    f: ENTER p=0x601058(2) n=3 level=2 
     f: ENTER p=0x60105c(3) n=2 level=3 
     f: ENTER p=0x601060(4) n=1 level=4 
     f: EXIT ret=0 level=4 
     f: SUBVAL val=0 pp=2 
     f: EXIT ret=2 level=3 
    f: SUBVAL val=2 pp=-4 
    f: EXIT ret=2 level=2 
    f: SUBVAL val=2 pp=3 
    f: EXIT ret=3 level=1 
f: SUBVAL val=3 pp=-2 
f: EXIT ret=3 level=0 
RESULT: 3