递归下降乘法实现：如何打印递归调用的返回过程？

问题描述 #

需要实现递归乘法的递归下降过程打印，同时打印递归调用的返回过程，输入参数为(100, 37)。目前已能打印递归下降过程，但无法实现返回过程的打印。

预期输出 #

Descent:
In recursive descent, the first value is a, the second value is b.
100 37
200 18
400 9
800 4
1600 2
3200 1

Return from recursive calls:
Here first result, second a, fourth new_result. The third one is not needed yet.
3200
3200 1600 0 3200
3200 800 0 3200
3200 400 1 3600
3600 200 0 3600
3600 100 1 3700
3700

现有代码问题 #

原代码直接返回递归调用的结果，无法在递归返回后执行打印逻辑；b<0分支未返回值，存在逻辑漏洞；缺少返回过程的打印处理。

修改后的实现代码 #

#include <stdio.h>

// 静态变量控制返回标题仅打印一次
static int printed_return_header = 0;

int rusMult(int a, int b)
{
    int res, ost, new_res;
    
    // 处理负数乘数，转为正数递归
    if (b < 0) 
    {
        return rusMult(a, -b);
    }
    
    // 递归终止条件：乘数为0时返回0
    if(b == 0)
    {
        return 0;
    }
    
    ost = b % 2; // 提前计算乘数的奇偶性
    
    // 打印递归下降过程的a和b
    printf("%d %d\n", a, b);
    
    // 先保存递归调用结果，不直接返回
    res = rusMult(a * 2, b / 2);
    
    // 打印返回过程的标题，仅执行一次
    if (!printed_return_header) {
        printf("\nReturn from recursive calls:\n");
        printf("Here first result, second a, fourth new_result. The third one is not needed yet.\n");
        printed_return_header = 1;
    }
    
    // 根据奇偶性计算当前层的结果
    new_res = ost ? (res + a) : res;
    
    // 按预期格式打印返回过程
    if (b == 1) {
        printf("%d\n", new_res);
    } else {
        printf("%d %d %d %d\n", res, a, ost, new_res);
    }
    
    return new_res;
}

int main()
{
    int result;
    // 打印下降过程的标题
    printf("Descent:\n");
    printf("In recursive descent, the first value is a, the second value is b.\n");
    // 调用递归函数并获取结果
    result = rusMult(100, 37);
    // 打印最终返回结果
    printf("%d\n", result);
    return 0;
}

关键改动说明 #

1. 保存递归结果：将递归调用的结果存入res变量，而非直接返回，确保递归返回后能执行打印逻辑。
2. 控制标题打印：用静态变量printed_return_header确保返回过程的标题仅打印一次，避免递归重复输出。
3. 统一奇偶处理：提前计算b%2的结果ost，简化后续的结果计算与打印逻辑。
4. 修复逻辑漏洞：补全b<0分支的返回值，保证函数逻辑完整性。
5. 分情况打印返回过程：针对b=1的最底层非终止情况单独打印返回值，其他情况按res a ost new_res格式打印。

内容的提问来源于stack exchange，提问作者Евгений Смирнов