第七章递归知识讲解。（一）

package 第七章递归知识讲解;
/**
 * 递归的定义：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，
发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，
你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。循环
：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（
若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一
直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。上面的比喻形象地阐述了递归与循环的内涵，那么我们来思
考以下几个问题：
什么是递归呢？
递归的精髓(思想)是什么？
递归和循环的区别是什么？
什么时候该用递归？
使用递归需要注意哪些问题？递归思想解决了哪些经典的问题？
这些问题正是笔者准备在本文中详细阐述的问题。
二. 递归的内涵1、定义 (什么是递归？)在数学与计算机科学中，递归(Recursion)是指在函数
的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。
2、递归思想的内涵(递归的精髓是什么？)正如上面所描述的场
景，递归就是有去（递去）有回（归来）
，如下图所示。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就
像上面例子中的钥匙可以打开后面所有门上的锁一样；“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，
就不用再往更小、更远的地方走下去。
最后，从这
个临界点开始，原路返回到原点，原问题解决。
 * @author MZFAITHDREAM
 *
 */
public class 递归0 {
/**
 * 什么是递归自己调用自己,利用加法。来看看什么是递归
 * @param args
 */
  public static void main(String[] args) {
  // TODO Auto-generated method stub
  int n=sum_recursion(1, 3);
  //1+2+3+4+5+6=21
  System.out.println(sum_recursion(n, n));
  /**
   * @author MZFAITHDREAM
   * 定义一个- 法
   */
  int m=sum_recursion1(6, 1);
  System.out.println(sum_recursion1(m, m));
  }
  private static int sum_recursion1(int end, int start) {
    if(end==start) {
    return start;
    } 
    return end-sum_recursion1(end-1, start);
}
  private static int sum_recursion(int start,int end) {
  // TODO Auto-generated method stub
    if(start==end) {
      return end;
    }
//    自己调用自己
    return start+sum_recursion(start+1, end);
    }
}

package 第七章递归知识讲解;
/**
 * 第七章第一课
 * 7.2 双管齐下解决递归问题
 * 上楼梯问题
 * @author MZFAITHDREAM
 *
 */
public class 递归2 {
  public static void main(String[] args) {
  System.out.println(f1(39));
  }
  //用递归
  public static long f1(int n) {
  if(n<0) return 0;
  if(n==0||n==1) return 1;
  if(n==2) return 2;
  return f1(n-1)+f1(n-2);
  }
}

package 第七章递归知识讲解;
/**
 * 7.4 名企面试题：硬币表示某个给定数值
 * 循环中递归
 * @author MZFAITHDREAM
 *
 *
假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，
用这些硬币组合够成一个给定的数值n。例如n=200，那么一种可能的组合
方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100.
问总共有多少种可能的组合方式？
2、华为面试题
1分2分5分三种硬币，组成已一角/共有多少解法
3.cc150 给出 1 5 10 25 有多少种方法
*/
public class 递归3 {
  public static void main(String[] args) {
  int res=countWays(15);
  System.out.println(res);
  }
   public static int countWays(int n) {//输入面值
    if(n<=0) {//如果小于零
     return 0;
    }//定义总价    数组面值        下标
    return countWaysCore(n,new int[] {1,2,5,10,20,50,100,200},7);
   }//代入
   private static int countWaysCore(int n,int[]coins,int cur) {
    if(cur==0) {
     return 1;
    }
    int res=0;
         //要么不选， 可以选1 2  3 4 
    for(int i=0;i*coins[cur]<=n;i++) {//100 25 *4 i
    int shenyu=n-i*coins[cur];//取大的多少个
      res+=countWaysCore(shenyu,coins,cur-1);//递归+
  }
  return res;  
   }
}