写递归

总结的写递归的几种方法：

1. 第一种是直接有递推公式，那么就直接找停止条件就好了，但是要注意停止条件的严谨性。如果条件不严谨可能会出现死循环的情况。
   比如 斐波那契数列：f(n)=f(n-1)+f(n-2)
   最大公约数：f(m, n) = f(n, m\%n)

2. 如果递推公式不是很明确可以通过一个范式找到递归方法。首先明确函数功能是什么，然后去找停止条件，最后利用这个函数在变化里找重复，再在重复里找变化，一般是不断缩小参数的范围。
   注意这个参数有的时候需要额外传入：
   反转字符串：

static String f(String myString, int begin) {
    
    if (begin == myString.length()-1) {
        return myString.charAt(begin)+"";
        
    }
    return f(myString, begin+1)+myString.charAt(begin);
}

在这里这个 begin 就是一个递归变量，如果不使用这个参数的话，还有一个办法就是在递归过程中创建一个新的字符串（比原字符串少一个char），直接递归字符串，但是这样的话就要创建很多额外的字符串，占用大量的内存。

另外需要注意递归问题的几种形式，第一种就是向上面例子一样的单路径的递归，或者是像汉诺塔或者斐波那契数列这种的双分支递归，还有可能是类似于双分支递归，但是会有判断舍弃掉一半，比如二分查找的递归写法。

static void hano(int k, String from, String to, String help) {
    if (k == 1) {
        System.out.println("move "+k+" from "+from+" to "+to );
        return;
    }

    hano(k-1, from, help, to);
    System.out.println("move "+k+" from "+from+" to "+to );
    hano(k-1, help, to, from);

}

private static int binerySearch(int[] arr, int low_index, int hight_index, int key){
    if (low_index>hight_index) {
        return -1;
    }
    int mind_index = (low_index+hight_index)>>>1;
    int midVal = arr[mind_index];
    if (midVal<key) {
        return binerySearch(arr, mind_index+1, hight_index, key);
    }
    else if (midVal > key) {
        return binerySearch(arr, low_index, mind_index-1, key);
    }
    else {
        return mind_index;
    }
}