C语言双重递归概念详解及1/1!+2/2!+…+n/n!序列实现示例

1. 逻辑类比问题解答 #

你理解的递归嵌套递归和二维数组循环嵌套循环结构类似的结论是完全正确的：

• 外层递归对应外层for循环：负责遍历序列的每一项（从1到n），每完成一次外层递归的步进，就触发一次内层递归的完整执行
• 内层递归对应内层for循环：负责完成单次迭代内的计算任务（本题中就是计算当前项的阶乘），内层递归全部执行完毕返回结果后，才会继续外层递归的下一次步进

2. 你的实现评估 #

你的思路完全符合题目要求：用外层递归numerator遍历每一项，内层递归denominator计算阶乘，是标准的嵌套式双重递归实现，仅存在少量C语法问题：

1. 函数定义缺失返回值类型：声明时写了int numerator(int,int)，定义时没有写int前缀
2. 递归函数缺失返回语句：denominator的递归分支没有写return，会导致返回值异常

3. 修正后的可运行代码 #

#include<stdio.h>
int numerator(int,int);
int denominator(int,int);
int main()
{
    int n=0, i=1;
    printf("Please enter the last number of your series : ");
    scanf("%d", &n);
    numerator(i,n);
    return 0;
}
// 外层递归：遍历输出每一项
int numerator(int i,int n)
{
    int d=1;
    if (i<=n)
    {
        if (i==n)
        {
            printf(" %d/%d",i,denominator(d,i));
        }
        else
        {
            printf(" %d/%d +",i,denominator(d,i));
            i++;
            numerator(i,n);
        }
        return 0;
    }
    else
    {
        return 0;
    }
}
// 内层递归：计算阶乘
int denominator(int d,int i)
{
    if (i==1)
    {
        return d;
    }
    else
    {
        d=d*i;
        i--;
        return denominator(d,i);
    }
}

4. 扩展双重递归场景 #

除了你用到的嵌套式双重递归，还有一种常见的双重递归形式是单递归函数内两次调用自身，逻辑上类似二叉树遍历，典型示例为斐波那契数列计算：

// 计算第n项斐波那契数
int fib(int n) {
    if(n <= 1) return n;
    // 单次函数内两次递归调用自身，也属于双重递归范畴
    return fib(n-1) + fib(n-2);
}

内容的提问来源于stack exchange，提问作者Hamza Khan