时间戳

首页 > 解决方案 > 如何使交互式链表函数递归

c - 如何使交互式链表函数递归

问题描述

我在寻找使迭代函数成为递归函数的方法时遇到了这个问题。

它是关于一个链表，这个链表存储了“收藏”的视频，每个视频都有一个声音，我们要统计所有包含指定声音的视频。

链表元素如下所示：

typedef struct {
    tVideo video;    
} tFavorite; 

// Data type to hold data related to a video in the platform
typedef struct tNode {
    tFavorite e;
    struct tNode *next;
} tFavoriteStackNode;

// Definition of a stack of favorites
typedef struct {
    tFavoriteStackNode *first;
} tFavoriteStack;

并且 tVideo 有声音（video.sound）。

现在，迭代函数是这样的：

unsigned favoriteStack_getFavoritesPerSoundRecursive(tFavoriteStack *stack, tSound *sound){
    // PR2 EX3
    assert(stack != NULL);
    tFavoriteStackNode *tmp = (tFavoriteStackNode*)malloc(sizeof(tFavoriteStackNode));
    static int cont = 0;
    if (favoriteStack_empty(*stack)) {
        return cont;
    }
    else {
        tmp = stack->first;
        while (tmp != NULL) {
            if (tmp->e.video.sound != NULL){
                if (sound_equals(sound, tmp->e.video.sound)){
                    cont++;
                }
            }
            tmp = tmp->next;
        }
    }
    return cont;
}

在这种情况下，我们做一个while循环，每次都将节点更改为下一个。 （请注意，if (tmp->e.video.sound != NULL) 由于 sound_equals() 中的断言而被调用）

所以我的问题是我怎样才能把这个函数变成一个递归函数？

提前致谢，

琼·弗雷克斯

标签： crecursioniteration

解决方案

unsigned tFavoriteStackNode_numSoundRecursive (
    tFavoriteStackNode *node, 
    tSound *sound
){
    if (node == NULL) // stop recursion
        return 0;
        
    // assuming sound_equals returns a boolean value (0: false, 1: true)
    // need something different if a e.g. -1 could be returned in case of some error
    unsigned eq = (node->e.video.sound != NULL) 
                  ? sound_equals(sound, node->e.video.sound) 
                  : 0;
    return (
        eq +
        tFavoriteStackNode_numSoundRecursive (
            node->next, 
            sound
        )
    );
}
        
unsigned favoriteStack_getFavoritesPerSoundRecursive (
    tFavoriteStack *stack, 
    tSound *sound
){
    assert(stack != NULL);
    
    if (favoriteStack_empty(*stack)) //sure about dereferencing?
        return 0;
        
    return tFavoriteStackNode_numSoundRecursive(stack->first);
}

@Code Apprentice - 递归终止得太早了，我意识到，现在应该是正确的。

推荐阅读