欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

死磕算法-递归行为的实质

程序员文章站 2022-07-12 08:12:05
...

概述

递归用一句话概括,就是自己调用自己,而实现就是通过系统栈对函数的出栈和压栈操作。


用一个例子解释下递归的背后的实现

	public static int getMax(int[] arr,int left,int right) {
		if(left==right) {
			return arr[left];
		}
		int mid = (left+right)/2;
		int maxLeft=getMax(arr,left,mid);
		int maxRight=getMax(arr,mid,right);
		return Math.max(maxLeft, maxRight);
	}

假设此时有这样一个数组{4,2,1,3},传入getMax(),left=0,right=3

  1. 判断left!=right,执行下一步
  2. 计算出mid为1
  3. 尝试获取maxLeft,进入getMax(arr,left,mid)之前,先将一开始调用的函数入栈(存入参数值mid=1,程序计数器保存函数当前执行到第几行)
  4. 第二次调用getMax后,传入的参数是(arr,left=0,right=mid=1),重复第二步计算mid,重复第三步进入getMax,并压栈
    死磕算法-递归行为的实质
    直到left==right,开始返回,系统栈开始弹栈,栈顶的函数先出栈,即getMax(arr,0,1),mid=0这个栈元素出栈,继续往下执行第x+1行,即int maxRight=getMax(arr,mid,right);,传入arr,mid=0,right
    死磕算法-递归行为的实质
    之后继续执行第x+1行
    死磕算法-递归行为的实质
    直到递归完成。

递归用起来很好理解,要理解背后的执行流程就比较复杂,读者大概知道递归就是系统在不断地帮我们压栈出栈即可,每次压栈的信息包括程序计数器的内容(即函数执行到第几行),还有参数信息
可以简单理解下图
死磕算法-递归行为的实质


递归的时间复杂度:master公式的使用

T(N) = a*T(N/b) + O(Nd(额外时间复杂度)

  • log(b,a) > d -> 复杂度为O(Nlog(b,a)
  • log(b,a) = d -> 复杂度为O(N^d * logN)
  • log(b,a) < d -> 复杂度为O(Nd

其中b:N/b为子样本容量,a为划分的样本个数
还是用一这例子解释下这个master公式

public static int getMax(int[] arr,int left,int right) {
		
		if(left==right) {
			return arr[left];
		}
		
		int mid = (left+right)/2;
		int maxLeft=getMax(arr,left,mid);
		int maxRight=getMax(arr,mid,right);
		return Math.max(maxLeft, maxRight)	
	}

这里子样本容量为原样本容量的1/2,所以b为2;执行了两次子递归,所以a为2
这样的话,对数结果为1 ,而此处额外时间复杂度为1,因此1==1,符合第二种情况,之后代入公式即可。