写递归

时间:2021-6-7 作者:qvyue

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

  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, low_index, mind_index-1, key);
    }
    else {
        return mind_index;
    }
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。