老赵赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个 村子后还剩 n 只鸭子，问他出发时共赶多少只鸭子？

Question

老赵赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个
村子后还剩 n 只鸭子，问他出发时共赶多少只鸭子？

Answer 1

1.题目分析
将下列题目采用递归和非递归的方式实现
(1)一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
(2)角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
2.算法构造:
(1)递归：由于每个村子卖鸭子的规律是相等的，都是卖去所有鸭子的一半又一只。且经过7次后还剩下俩只。所以根据条件可设计递归模型为。
2 n=0
Fun(n)=
2* (f(n-1)+1) n>0

非递归：采用for循环。由于经过几个村子卖几次。所以循环的次数就为n次。然后设置变量sum用来表示鸭子的总数量，每一次循环sum=(sum+1)2;
(2)递归：输入一个自然数。如果非一时，奇数就乘三加一，偶数就除以二。经过多次后总可以得到1.。根据条件可以设计递归模型为，count为该数经过的次数
count m=1
fun(m)= fun(3(m-1)+1) m%2!=0&&m!=1
fun(m/2) m%2==0
非递归：采用while循环，如果输入的数不等于1，就进入循环。如果他是奇数，就执行m=3*m+1.如果是偶数，就执行m=m/2；
3.算法实现
源代码：

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println(“请输入经过村子的个数：”);
int number=sc.nextInt();
SellDuck s=new SellDuck();
System.out.println(s.recursion(number));
System.out.println(s.norecursion(number));
jiaogu j=new jiaogu();
int m=0;
while(m<=0){
System.out.println(“请输入一个大于0的数字：”);
m=sc.nextInt();
}
System.out.println(j.recursion(m));
System.out.println(j.norecursio(m));
}

}

class SellDuck{
public int recursion(int n){
if(n==0){
return 2;
}else if(n>0){
return (2*(recursion(n-1)+1));
}else{
return -1;
}
}

public int norecursion(int n){
    int sum=2;
    for(int i=1;i<=n;i++){
        sum=(sum+1)*2;
    }
    return sum;
}
}

class jiaogu{
static int count1=0;
static int count2=0;
public int recursion(int m){
if(m==1){
System.out.print(m+" “);
return ++count1;
}else if(m%2!=0){
System.out.print(m+” “);
count1++;
return recursion(3*m+1);
}else{
System.out.print(m+” ");
count1++;
return recursion(m/2);
}
}

public int norecursio(int m){
    while(m!=1){
        if(m%2!=0){
            System.out.print(m+" ");
            count2++;
            m=m*3+1;
        }else{
            System.out.print(m+" ");
            count2++;
            m/=2;
        }
    }
    System.out.print(m+" ");
    return ++count2;
}
}

4.经验归纳
递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。
递归算法：
优点：代码简洁、清晰，并且容易验证正确性。
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理，比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。
循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。