递归-JZTXT

递归

在函数中调用自身函数的方法。函数一直在调用自己，层层嵌套。

1.如何培养递归中的逆向思维

如何计算n!

迭代版：正向思维

首先定义一个result变量，result=1。让i循环n次，每次result*i。

long factorial(int n)
{
	int result = 1;
	for (int i = 1; i <= n; i++)
	{
		result = result * i;
	}
	//while (n > 1)
	//{
	//	result *= n;
	//	n -= 1;
	//}
	return result;
}

递归版：逆向思维

要求5！,就必须知道4！，然后以此类推，到0！。
从最终想要的答案出发，逐步向前寻找上一层的答案，并且用他们构造当前层的答案。

设计一个函数，当n=0时，直接返回1，作为基础情况，然后递归的调用这个函数求得（n-1）!,然后再乘以n,便求得了n!。

代码如下:

long factorial(int n)
{
	if( n<=0 ) return 1;
	else return n*factorial(n-1);
}

实现斐波那契数列

斐波那契数列指的是这样一个数列：
0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711……
它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。
在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），显然，斐波那契数列是一个线性递推数列。

迭代：

参考Fibnonacci

int finbonacci(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1 || n == 2)
		return 1;
	int n1 = 1, n2 = 1, sum = 0;
	for (int i = 2; i < n; i++)
	{
		sum = n1 + n2;
		n1 = n2;
		n2 = sum;
	}
	return sum;
}

递归

递归树构成：

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

关于归并排序的递归：

对左右子数组分别排序，然后将两个有序数组合并为一个。

点击查看代码

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 1e5 + 10;
int a[N], temp[N];
using namespace std;
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) >> 1;//默认向下取整
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);//递归时mid+1成为l，这里递归非常妙，分成一个一个的数

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] < q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];

    for (int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

2.如何治疗晕递归

递归函数定义

明确函数使命
明确原问题与子问题
兼顾原问题与子问题

不要去深究超级操作的内部细节，坚定不移相信它。

数学归纳法与递归相似之处

归纳奠基：证明n=1时某个命题成立
归纳假设：假设n=k时命题也成立
归纳递推：由归纳假设推导出n=k+1时命题也成立
如果三个步骤满足，便可证明n等于任何正整数命题都成立。

3.汉诺塔问题

用二进制来解汉诺塔问题
汉诺塔是一个经典的递归问题