c - 如何跟踪这个 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