このC再帰プログラムをトレースする方法

Question

再帰のトピックには新しく、以下のCプログラムのトレースを概念化するのは難しいです。リソースを提供する際の援助やそれをトレースする方法についての説明は非常に高く評価されます。

#include <stdio.h> 

int multiply(int x, int y); 

int exponent(int x, int y); 
int exponent(int x, int y) { 
    if (y == 0){ 
     return 1; 
    } else { 
     int i = exponent(x,y-1); 
     int n = multiply(x,i); 
     return n; 
    } 
} 

int multiply(int x, int y) { 

if (y == 0 || x == 0){ 
    return 0; 
} 

if (y > 0) { 
    return x + multiply(x,y-1); 
} 
else { 
    return -x + multiply(x,y+1); 
} 
} 

int main() { 
printf("3^5 = %i\n", exponent(3, 5)); 
} 

Answer 1

数学的には、再帰は数学的帰納と似ています。再帰を使用する場合は、何が基本ケースであり、何が再帰呼び出しであるかを覚えておいてください。事実上調査することはそれほど多くありません。ここでは適切なデバッグ文を追加しました。再帰関数の呼び出しによってどのように再帰が構築され、最終的には再帰を中断するベース・ケースに達することで中断されるかを確認できます。

#include <stdio.h> 

int multiply(int x, int y); 

int exponent(int x, int y); 
int j = 0; 
int exponent(int x, int y) { 
    if (y == 0){ 
     return 1; 
    } else { 
     printf("depth:%d x:%d y:%d\n", j, x, y); 
     j++; 
     int i = exponent(x,y-1); 

     int n = multiply(x,i); 
     return n; 
    } 
} 
int k = 0; 
int multiply(int x, int y) { 

    if (y == 0 || x == 0){ 
     return 0; 
    } 

    if (y > 0) { 
     printf("depth multiply:%d x:%d y:%d\n", k, x, y); 
     k++; 
     return x + multiply(x,y-1); 
    } 
    else { 
     printf("depth multiply:%d x:%d y:%d\n", k, x, y); 
     k++; 
     return -x + multiply(x,y+1); 
    } 
} 

int main() { 
    printf("3^5 = %i\n", exponent(3, 5)); 
} 

出力

depth:0 x:3 y:5 
depth:1 x:3 y:4 
depth:2 x:3 y:3 
depth:3 x:3 y:2 
depth:4 x:3 y:1 
depth multiply:0 x:3 y:1 
depth multiply:1 x:3 y:3 
depth multiply:2 x:3 y:2 
depth multiply:3 x:3 y:1 
depth multiply:4 x:3 y:9 
depth multiply:5 x:3 y:8 
depth multiply:6 x:3 y:7 
depth multiply:7 x:3 y:6 
depth multiply:8 x:3 y:5 
depth multiply:9 x:3 y:4 
depth multiply:10 x:3 y:3 
depth multiply:11 x:3 y:2 
depth multiply:12 x:3 y:1 
depth multiply:13 x:3 y:27 
depth multiply:14 x:3 y:26 
depth multiply:15 x:3 y:25 
depth multiply:16 x:3 y:24 
depth multiply:17 x:3 y:23 
depth multiply:18 x:3 y:22 
depth multiply:19 x:3 y:21 
depth multiply:20 x:3 y:20 
depth multiply:21 x:3 y:19 
depth multiply:22 x:3 y:18 
depth multiply:23 x:3 y:17 
depth multiply:24 x:3 y:16 
depth multiply:25 x:3 y:15 
depth multiply:26 x:3 y:14 
depth multiply:27 x:3 y:13 
depth multiply:28 x:3 y:12 
depth multiply:29 x:3 y:11 
depth multiply:30 x:3 y:10 
depth multiply:31 x:3 y:9 
depth multiply:32 x:3 y:8 
depth multiply:33 x:3 y:7 
depth multiply:34 x:3 y:6 
depth multiply:35 x:3 y:5 
depth multiply:36 x:3 y:4 
depth multiply:37 x:3 y:3 
depth multiply:38 x:3 y:2 
depth multiply:39 x:3 y:1 
depth multiply:40 x:3 y:81 
depth multiply:41 x:3 y:80 
depth multiply:42 x:3 y:79 
depth multiply:43 x:3 y:78 
depth multiply:44 x:3 y:77 
depth multiply:45 x:3 y:76 
depth multiply:46 x:3 y:75 
depth multiply:47 x:3 y:74 
depth multiply:48 x:3 y:73 
depth multiply:49 x:3 y:72 
depth multiply:50 x:3 y:71 
depth multiply:51 x:3 y:70 
depth multiply:52 x:3 y:69 
depth multiply:53 x:3 y:68 
depth multiply:54 x:3 y:67 
depth multiply:55 x:3 y:66 
depth multiply:56 x:3 y:65 
depth multiply:57 x:3 y:64 
depth multiply:58 x:3 y:63 
depth multiply:59 x:3 y:62 
depth multiply:60 x:3 y:61 
depth multiply:61 x:3 y:60 
depth multiply:62 x:3 y:59 
depth multiply:63 x:3 y:58 
depth multiply:64 x:3 y:57 
depth multiply:65 x:3 y:56 
depth multiply:66 x:3 y:55 
depth multiply:67 x:3 y:54 
depth multiply:68 x:3 y:53 
depth multiply:69 x:3 y:52 
depth multiply:70 x:3 y:51 
depth multiply:71 x:3 y:50 
depth multiply:72 x:3 y:49 
depth multiply:73 x:3 y:48 
depth multiply:74 x:3 y:47 
depth multiply:75 x:3 y:46 
depth multiply:76 x:3 y:45 
depth multiply:77 x:3 y:44 
depth multiply:78 x:3 y:43 
depth multiply:79 x:3 y:42 
depth multiply:80 x:3 y:41 
depth multiply:81 x:3 y:40 
depth multiply:82 x:3 y:39 
depth multiply:83 x:3 y:38 
depth multiply:84 x:3 y:37 
depth multiply:85 x:3 y:36 
depth multiply:86 x:3 y:35 
depth multiply:87 x:3 y:34 
depth multiply:88 x:3 y:33 
depth multiply:89 x:3 y:32 
depth multiply:90 x:3 y:31 
depth multiply:91 x:3 y:30 
depth multiply:92 x:3 y:29 
depth multiply:93 x:3 y:28 
depth multiply:94 x:3 y:27 
depth multiply:95 x:3 y:26 
depth multiply:96 x:3 y:25 
depth multiply:97 x:3 y:24 
depth multiply:98 x:3 y:23 
depth multiply:99 x:3 y:22 
depth multiply:100 x:3 y:21 
depth multiply:101 x:3 y:20 
depth multiply:102 x:3 y:19 
depth multiply:103 x:3 y:18 
depth multiply:104 x:3 y:17 
depth multiply:105 x:3 y:16 
depth multiply:106 x:3 y:15 
depth multiply:107 x:3 y:14 
depth multiply:108 x:3 y:13 
depth multiply:109 x:3 y:12 
depth multiply:110 x:3 y:11 
depth multiply:111 x:3 y:10 
depth multiply:112 x:3 y:9 
depth multiply:113 x:3 y:8 
depth multiply:114 x:3 y:7 
depth multiply:115 x:3 y:6 
depth multiply:116 x:3 y:5 
depth multiply:117 x:3 y:4 
depth multiply:118 x:3 y:3 
depth multiply:119 x:3 y:2 
depth multiply:120 x:3 y:1 
3^5 = 243