Algorithm：递归思想及实例分析

目录

• 递归思路
• T 1：求阶乘
• T 2：求数组元素和
• T 3：斐波那契数列
• T 4：最大公约数
• T 5：插入排序改递归
• T 6：汉诺塔问题
• T 7：二分查找的递归算法
• T 8：小白上楼梯
• T 9：求a的n次幂
• 递归性能
• 总结

递归思路

1、找重复：找出子问题

2、找变化：变化的量应该作为参数；

3、找边界：设计函数的出口；

T 1：求阶乘

输入n，使用递归的方法输出n！

int Rec(int n)
{
    if(n==1)
        return 1;
    return n*Rec(n-1);
}

T 2：求数组元素和

对arr的所有元素求和

int Rec(vector<int> arr,int begin)
{
    if (begin == arr.size() - 1)
        return arr[begin];
    return arr[begin] + Rec(arr,begin + 1);
}

T 3：斐波那契数列

f(0)=1

f(1)=1

f(2)=f(0)+f(1)=2

f(3)=f(1)+f(2)=3

f(n)=f(n-2)+f(n-1)

输入n，求f(n)

int Feb(int n)
{
    if(n==0 || n==1)
        return 1;
	return Feb(n-2)+Feb(n-1);	
}

T 4：最大公约数

输入m，n，求它俩的最大公约数(m>n)

int Rec(int m,int n)
{
    if(n==0)
        return n;
    return Rec(n,m%n)
}

T 5：插入排序改递归

使用递归的方法对数组arr进行排序；

void insertSort(vector<int> &arr, int pos)//对arr[0]-arr[pos]进行排序
{
	if (pos == 0)
		return;

	insertSort(arr, pos - 1);//等pos前面的元素都排序完了，我再对pos元素进行排序；
	int p = pos;
	int val = arr[p];
	while (p > 0 && val < arr[p - 1])//只要比前面的元素小，就继续向前找位置
	{
		arr[p] = arr[p - 1];
		p--;
	}
    //此时arr[p]>arr[p-1]，在此位置插入；
	arr[p] = val;
}

T 6：汉诺塔问题

A B C三处，将A处的n个盘子移动到C处，每次只能移动1个盘子，下盘子只能放在大盘子上面；

1、找重复：把n块盘子从A移动到C，那么我只需叫人通过中介C帮我把n-1个盘子移动到B处，然后我把第n个盘子移动到C处，再叫别人把B处的n-1个盘子通过中介A挪到C处；

2、找变化：移动过程中，初始地、中介、目的地以及目前移动的哪块盘子都不一样，这些都是变化量；

3、找边界：如果n==0时，不存在第0块盘子，所以此时什么都不用做，返回即可；

void Hanuo(int n, char begin, char help, char dest)
{
	if (n < 1)
		return;
	Hanuo(n - 1, begin, dest, help);
	cout << "move " << n << " from " << begin << " to " << dest << endl;
	Hanuo(n - 1, help, begin, dest);
}
int main()
{
	Hanuo(3, 'A', 'B', 'C');
	return 0;
}

T 7：二分查找的递归算法

对于有序数组arr，输入key，使用递归形式的二分查找方法查找key所对应的索引；

int BinarySearch(vector<int> arr, int left, int right, int key)
{
    if(left > right) //此时表示在数组arr中找不到该key值
        return -1;
    //二分查找
	int mid = left + (right - left) / 2;
	if (arr[mid] == key)
		return mid;
	else if (arr[mid] < key)
	{
		return BinarySearch(arr, mid + 1, right, key);
	}
	else
	{
		return BinarySearch(arr, left, mid - 1, key);
	}
}

T 8：小白上楼梯

小白正在上楼梯，楼梯有n阶，小白一次可以上1阶、2阶或者3阶，实现一个方法，计算小白有多少种走完楼梯的方式；

int Dec(int n)
{
	//边界条件
	if(n==1)
		return 1;
	if(n==2)
		return 2;
	if(n==3)
		return 4;
	//递归
	return Dec(n-3)+Dec(n-2)+Dec(n-1);
} 

T 9：求a的n次幂

设计一个高效的求a的n次幂的算法

2⁴=2 * 2 * 2 * 2 =16；
2² * 2² =16;
如果指数是2的倍数，说明aⁿ可以直接用 a^n/2 * a^n/2 算出；
如果指数非2的倍数，则aⁿ可以直接用 a^n/2 * a^n/2 * a 算出(多乘一个a)；
常规的递归求幂需要O(N)的时间复杂度，而这种方法只需O(log N);

int Dec(int a,int n)
{
	if(n==0)
		return 1;
	if(n%2==0) 
	{
		int temp=Dec(a,n/2);
		return temp*temp;
	}
	else
	{
		int temp=Dec(a,n/2);
		return temp*temp*a;
	}	 
} 

递归性能

递归的时间复杂度取决于子问题的分支数；

比如求阶乘的时间复杂度为O(n)，而斐波那契时间复杂度大约为O(2ⁿ);

因为分支数越多意味着有更多的冗余运算，即多做了很多次重复的计算，这是就需要动态规划或者非递归的迭代形式来降低复杂度；

由于递归重复调用当前函数，函数主要使用栈空间，所以递归的空间复杂度也较高；

但递归有个最大的好处就是：容易理解；

总结

递归就是偷懒：

​ 我解决问题的一个部分，剩下的交给别人处理；或者理解为一个蛋糕，我只切一小块，剩下的怎么分交给别人完成；