【Weiss】【第03章】练习3.11：比较单链表递归与非递归查找元素

【练习3.11】

编写查找一个单链表特定元素的程序。分别用递归和非递归实现，并比较它们的运行时间。

链表必须达到多大才能使得使用递归的程序崩溃？

Answer:

实现都是比较容易的，但是实际上查找链表元素本身也没必要使用递归的方法。

考虑到题目让人比较运行时间与程序崩溃的边界，可以认为这是警示大家不要滥用递归的题目【【

毕竟在算法本身足够简单的时候，递归压栈会浪费大量额外空间与时间。

个人设备实测下，链表长度约5000时递归查找即崩溃，而迭代可在1000000长度的链表下正确运行。

测试代码如下：

 1 #include <iostream>
 2 #include "linklist.h"
 3 using linklist::List;
 4 using namespace std;
 5 int main(void)
 6 {
 7     List<int> number;
 8     for (int i = 0; i < 10; ++i)
 9         number.additem(i);
10     //测试两种查找的结果
11     cout << (number.find(1) == number.find_recursive(1)) << endl;
12     cout << (number.find(3) == number.find_recursive(3)) << endl;
13     cout << (number.find(7) == number.find_recursive(7)) << endl;
14     cout << (number.find(8) == number.find_recursive(8)) << endl;
15     
16     //通过调整循环次数，确定链表多长时递归会溢出
17     for (int i = 0; i < 4500; ++i)
18         number.additem(20);
19     number.additem(40);
20     //取消下面两种查找的注释，测试各自在多长的链表下能够运行
21     //在个人的设备上，迭代算法循环百万次后仍可运行
22     //而递归算法约5000次时即会溢出
23     //number.find(40);
24     //number.find_recursive(40);
25 
26     system("pause");
27 }

View Code

实现代码如下：

 1 //练习3.11新增，递归查找链表元素
 2 template <typename T> Node<T>* List<T>::find_recursive(const T &item)
 3 {
 4     return findr(item, front);
 5 }
 6 template<typename T> Node<T>* List<T>::findr(const T &item, Node<T>* pos)
 7 {
 8     if (pos == nullptr || pos->data == item)
 9         return pos; 
10     else 
11         return findr(item, pos->next);
12 }

其中，find_recursive在模板内声明为public，使用时调用该函数。而findr在模板内为private，是实际运算的执行者。