将迭代函数转换为递归函数
我知道人们通常会反过来问这个问题，但我有以下问题：我有这个迭代函数，它计算包含数据值20的循环双链表中的所有节点。现在，我如何使这个递归，递归函数的基本情况（终止案例）是什么？ 任何帮助表示赞赏：
int count(node *start) { int c; c = 0; if(start == NULL) return 0; if((start->roll_no) == 20) c = 1; node *current = start; while(current->next != start) { if((current->next->roll_no) == 20){ c++; } current = current->next; } return c; } 我认为这应该有效（但请注意，它需要一个额外的参数来跟踪开始）：
int count(node *start) { return count_helper(start, start); } int count_helper(node *current, node *start) { int c; c = 0; if(current == NULL) return 0; if((current->roll_no) == 20) c = 1; if(current->next == start) return c; return (c + count_helper(current->next, start)); }
int count(struct node * ptr) { return ptr==NULL ? 0 : (ptr->roll_no == 20 ? 1:0) + count(ptr->next); }
更新：列表显示为循环。
int count(struct node * start, struct node * ptr) { return ptr==NULL || ptr->next == start ? 0 : (ptr->roll_no == 20 ? 1:0) + count(start, ptr->next); } /* to be called like: */ cnt = count (the_list, the_list);
更新2 :(未计算最后一个节点）
int count(struct node * start, struct node * ptr) { return ptr==NULL ? 0 : (ptr->roll_no == 20 ? 1:0) + ptr->next == start ? 0 : count(start, ptr->next); }
更新3：它确实需要一对额外的括号……
#include struct node { struct node *next; int roll_no; }; struct node nodes[8] = {{ nodes+1, 20} ,{ nodes+2, 0} ,{ nodes+3, 20} ,{ nodes+4, 0} ,{ nodes+5, 20} ,{ nodes+6, 0} ,{ nodes+7, 20} ,{ nodes+0, 0} }; unsigned count(struct node * start, struct node * ptr) { return ptr==NULL ? 0 : (ptr->roll_no == 20 ? 1:0) + (ptr->next == start ? 0 : count(start, ptr->next) ) ; } #define COUNT(p) count(p,p) int main (void) { unsigned cnt,idx; for (idx = 0; idx < 8 ; idx++) { cnt = COUNT (nodes+idx); printf ("count@%u = %u\n", idx, cnt); } return 0; }
int count_recursive (node* current, node* start) { if (current == NULL) return 0; if (current->next == start) return (current->roll_no == 20 ? 1 : 0); if (current->roll_no == 20) return count_recursive(current->next, start) + 1; else return count_recursive(current->next, start); } int count(node* start) { return count_recursive(start, start); }
基本情况是“列表为空”或“我们在列表的末尾”。 然后你通过采取列表的其余部分（没有我们刚刚看到的项目）并完成同样的事情来递归。
请注意，这不是尾递归（虽然它可能被优化为尾递归选项），因此它会增加堆栈并可能爆炸。
递归尾：
int count_recursive (node* current, node* start, int c) { if (current == NULL) return c; if (current->next == start) return (current->roll_no == 20 ? 1 : 0) + c; if (current->roll_no == 20) return count_recursive(current->next, start, c+1); else return count_recursive(current->next, start, c); } int count(node* start) { return count_recursive(start, start, 0); }
尾递归选项更有可能被编译器优化为循环，但是足够智能的编译器应该将它们都变成循环。
没有使这个递归，因为结构中没有递归，它已经是一个列表。
通常，因为递归有很多开销，所以你可以通过创建’level to do’的列表（或堆栈）来重写这样的函数到迭代。 您可以在堆栈上推送项目，然后循环您的例程直到堆栈为空，而不是递归调用该函数。
一个例子是列出文件树。 您也可以将目录名称推送到要处理的目录堆栈上，而不是以递归方式为每个找到的目录调用该函数。 这样，当你有一个深度嵌套的树时，你没有大量的目录句柄或迭代器或你正在使用的任何东西。
但这里没有一个适用，因为你根本没有树。
但是可以这样做：你可以用递归调用替换while ，但是你必须传递原始的start，或者使它成为全局，否则你不知道何时打破递归。 此外，尽管可能，如果你有一个很长的清单，你很快就会遇到麻烦。
这个怎么样 ：
int count(node *start){ if(!start) return 0; int countValue = 0; return count(start,start,&countValue); } int count(node *start, node *next, int *count){ if(start == next)//circular list so this is your base return *count; if(next->next->roll_no) == 20){ *count++; } return count(start,next->next,count); }
虽然修改输入参数的递归函数不是自定义的。
也不使用全局变量。
这是我能提出的第一种方法