算法-递归

目录

什么是递归？

递归基本知识

案例

---

什么是递归？

狭义：函数可以自己调用自己-代码层面

广义：问题可以划分为小问题，将所有小问题解决，再将结果汇总，大问题便解决了-思想层面

问题的复杂性取决于传递的参数和每次调用自身的次数

函数调用的本质

function A(a){
    return a;
}
 
function B(b){
    return A(5)+b;
}
 
B(10);
 
 

执行B方法，将调用B函数的地址和参数b=10压入栈，执行B方法，再将调用A方法的地址和参数参数a=5压入栈，再执行A方法，return返回时，返回的是上一个地址，也就是A（5）这个位置，将5代替了A（5），再从栈中取出b=10，再return到上一个地址

递归基本知识

方法的调用是栈的结构，在A方法中调用B方法，会把这两个方法入栈，先执行完B方法再执行A方法。

如何设计递归

• 找重复：找该问题规模更小的子问题
• 找变化：变化的量作为传递的参数
• 找边界：达到某个条件结束递归，避免死循环

切蛋糕思维，等价转换思维...

递归代码中展现的内容

递归出口的判断

+

将大问题分解一步后的解决方式（传参）

案例

求阶乘

static int f1(int num){
        if(num == 1) return 1;
        return num * f1(--num);
    }

重复：n！=n*（n-1）!

循环：n不断减小

边界：n=1时结束

打印i到j

 static void f2(int i,int j){
        if(i > j) return;
        System.out.println(i);
        f2(i+1,j);
    }

重复：i到j    i+1到j  ...

变化：i变化

边界：i不能大于j

数组求和

static int f3(int[] arr,int length){
        if(length == 0) return 0;
        return arr[length-1]+f3(arr,--length);
    }

字符串反转

 求ABCD的反转=求D+ABC的反转=求DC+AB的反转.....

static String f4(String str,int end){
        if(end == -1){
            return "";
        }
        return str.charAt(end)+f4(str,end-1);
    }

斐波那契序列

1 1 2 3 5 8 13 每一项是前两项的和，求第n项

 public static int f1(int n){
        if(n==1 || n==2) return 1;
        return f1(n-1) + f1(n-2);
    }

重复：每一项是前两项之和

变化：每项的的前两项序号变化

边界：前两位为1

斐波那契的递归树

 递归的顺序是  f(10)-f(9)-f(8)-f(7)...  是后序遍历 

最大公约数

假设有两个数x和y，存在一个最大公约数z=(x,y)，即x和y都有公因数z，
那么x一定能被z整除，y也一定能被z整除，所以x和y的线性组合mx±ny也一定能被z整除。（m和n可取任意整数）

对于辗转相除法来说，思路就是：若x>y，设x/y=n余c，则x能表示成x=ny+c的形式，将ny移到左边就是x-ny=c，由于一般形式的mx±ny能被z整除，所以等号左边的x-ny（作为mx±ny的一个特例）就能被z整除，即x除y的余数c也能被z整除。

//最大公约数
    static int f2(int m,int n){
        if(m % n == 0) return n;
        return f2(n,m%n);
    }

求m和n的最大公约数，假设为z，如果m能被z整除，n能被z整除，m%n的余数也能被z整除，如果z不是n，就需要缩小范围，m肯定比n大，n肯定比m%n的余数大，那么就从n和m%n这个范围内找

插入排序递归方式

对数组0-n排序  等价于  对数组的0-n-1个元素排序，把第n个元素插入到这个有序的序列中。

//思路2
static void f3(int[] arr,int k){
        //出口
        if(k == 0) return;
        //对前k-1个元素排序
        f3(arr,k-1);
        //把位置k的元素插入到前面的部分
        int x = arr[k]; //记录第k的元素
        int index = k-1;//前一个元素坐标
        while (index > -1 && x < arr[index]){ //从小到大排序，x与其他元素比较
            arr[index+1] = arr[index]; //k位置比k-1的元素小，就把k-1的元素放到k上
            index--;
        }
        arr[index+1] = x;
    }

插入排序的思路有很多，对于1 3 5 7 2这个数组

思路1：可以把待排序数字与每个进行比较和交换

1 3 5 7 2->1 3 5 2 7->1 3 2 5 7->1 2 3 5 7

思路2：交换是来回进行两次赋值，可看出方法1中很多赋值为2的操作是无效的，不如干脆最后只赋值一次

1 3 5 7 2->1 3 5 7 7->1 3 5 5 7->1 3 3 5 7->12 3 5 7

思路3：先比较找到属于2的坐标，然后将该位置以后的元素往后移动一个单位，再赋值过去

1 3 5 7 2->1 3 3 5 7->1 2 3 5 7

汉诺塔

将所有盘子从A移动到B，每次只能移动一个盘子，移动过程中不允许大盘子在小盘子上面。

将原问题划分是，划分后的子问题要和原问题有相同的形式。

思路

N从A移动到B，A是起始，B是终点，C是辅助

等价于

N-1从A移动到C，A为起始，C是重点，B是辅助

N从A移动到B

N-1从C移动到B，C是起始，B是重点，A是辅助

 依次类推

把N-1移动到C

等价于

把N-2移动到B

把N-1移动到C

把N-2移动到C

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

二分查找的递归形式

递归树的形式

求阶乘的就是单分支，求斐波那契的是多分支，而这一个就是从多分支中选择一条路。

斐波那契的子问题增长规模是以二的指数来增长。 

static int f(int[] arr,int low,int high,int key){
        if(low > high)
            return -1;
        int mid = (low + high) / 2;
        int midVal = arr[mid];
        if(midVal < key)
            return f(arr,mid+1,high,key);
        else if (midVal > key)
            return f(arr,low,mid-1,key);
        else
        return mid;
    }