递归程序设计（卖鸭子，角谷定理）
一．实验目的
- 掌握递归程序设计的方法。明确递归的概念，通过对问题的分析，找出递归关系以及递归出口以对问题进行递归结构设计；
- 掌握递归程序转换为非递归程序的方法。
二.实验内容
1.一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
2.角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
三. 题目分析及调试
1.递归：根据经过第x个村庄后剩余鸭子数与卖出鸭子数之和为刚到达第x个村庄鸭子数之和。设经过第x个村庄后剩余鸭子数为Duck（x）只，则刚到达本村时鸭子数为2*(Duck（x）+1)，卖出鸭子数为Duck（x）+2，则
。因此刚出发时共赶Duck（0）只鸭子；经过第七个村庄时，剩余鸭子数为2只，所以Duck（7）=2。
非递归：采用循环方法。经过第八个村庄后剩余0只鸭子，因此经过前一个村庄时剩余鸭子数为：第i-1个村庄剩余数=（第i个村庄剩余数+1）*2，第i个村庄卖出数=第i个村庄剩余数+2。
递归：
非递归：
2.递归：当输入值为1时，直接输出1且输出STEP=1，所以Jiaogu(1)=1,i=1;
当输出值不为1为偶数x时，先输出x值，记运算次数i++，递归Jiaogu(x/2,i)；当输出值不为1为奇数x时，先输出x值，记运算次数i++，递归Jiaogu(x*3+1,i)；
最终输出STEP=i。
非递归：判断输入值y是否为1时执行while循环体，当不为1时，判断y的奇偶性，进行不同的运算，累计执行次数；当y=1时，输出STEP=i。
递归：
非递归：
四.总结
在写递归方法遇到的问题主要是递归体的构造与变量的选定，有可能会进入死循环。但使用递归方法可以减少代码量，同时也更加灵活。主要是要找到递归出口与递归体，结构一般为if-else语句，递归体一般由一个或多个推导数学公式组成。