如何将统计指定音效视频的链表迭代函数改写为递归函数？

首先，先指出你当前迭代函数里的两个小问题：

• 你用malloc分配了tmp变量，但之后直接把stack->first赋值给它，导致这块内存没有被使用也没有释放，造成了内存泄漏。
• 使用static int cont会导致这个变量的值在多次调用函数时被保留，比如第一次调用返回3，第二次调用会直接在3的基础上累加结果，这显然不符合统计单次查询的预期。

接下来，我们用递归的核心思想——分治拆解来改写这个函数：把“统计整个链表的匹配数量”拆解成“统计当前节点是否匹配”加上“统计剩余链表的匹配数量”，直到遇到链表末尾（递归终止条件）。

递归实现代码 #

我们可以用一个辅助递归函数来处理节点的遍历，主函数负责对外接口的合法性检查：

// 辅助递归函数：从指定节点开始，统计匹配指定音效的视频数量
static unsigned countMatchingSounds(tFavoriteStackNode *currentNode, tSound *targetSound) {
    // 递归终止条件：当前节点为空，没有更多元素可统计，返回0
    if (currentNode == NULL) {
        return 0;
    }

    // 计算当前节点是否匹配目标音效
    unsigned currentMatch = 0;
    if (currentNode->e.video.sound != NULL) {  // 避免sound_equals的断言触发
        if (sound_equals(targetSound, currentNode->e.video.sound)) {
            currentMatch = 1;
        }
    }

    // 递归处理下一个节点，加上当前节点的匹配数
    return currentMatch + countMatchingSounds(currentNode->next, targetSound);
}

// 对外的递归统计函数
unsigned favoriteStack_getFavoritesPerSoundRecursive(tFavoriteStack *stack, tSound *sound) {
    assert(stack != NULL);

    // 如果栈为空，直接返回0
    if (favoriteStack_empty(*stack)) {
        return 0;
    }

    // 从栈的第一个节点开始启动递归统计
    return countMatchingSounds(stack->first, sound);
}

递归逻辑说明 #

1. 终止条件：当传入的currentNode为NULL时，说明已经遍历到链表末尾，没有更多节点需要检查，返回0。
2. 当前节点处理：判断当前节点的视频音效是否非空且与目标音效匹配，匹配则计数加1，否则加0。
3. 递归递推：将当前节点的匹配数，加上对下一个节点的递归调用结果，得到从当前节点开始的总匹配数。

对比原迭代函数的优势 #

• 没有使用static变量，每次函数调用都是独立计算，不会出现多次调用结果累计的问题。
• 解决了原函数的内存泄漏问题，不需要额外分配内存。
• 递归逻辑更贴合链表的结构特性，代码可读性更高，符合递归“分而治之”的思想。

内容的提问来源于stack exchange，提问作者Joan Freixas Arnedo