2.1递归

2019-11-04

2.1递归

概念：直接或间接的调用自身的算法成为递归算法。用函数自身给出定义的函数成为递归函数。

2-1阶乘函数。阶乘函数可递归的定义为

n！= 1（n = 0）/ n*(n-1)! (n>0)

递归的特变：

1.每个递归函数都必须有非递归定义的初始值，如上式n=0，n!=1.

2.第二式用较小自变量的函数值来表示较大自变量的函数值来定义n的阶乘

3.要有临界条件

例2-1

//factorial 阶乘 阶乘的 因子的
int factorial(int n) {
	if (n == 0)
		return 1;
	return n*factorial(n-1);
}

例2-2 斐波那契数列

/*
	无穷数列：1,1,2,3,5,8,13,21,34......
	递归定义为
				    1                   x = 0
			f(x) =  1                   x = 1
           			f(x-1) + (x-2)      x > 1
*/
int fibonacci(int n) {
	if (n <= 1)
		return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

例2-3 Ackerman函数（双递归）

int ack(int m,int n)
{
    if(m == 0)
        return n+1;
    else if(n == 0)
        return ack(m-1,1);
    else
        return ack(m-1,ack(m,n-1));
}

例2-4 全排列问题

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

void Perm(Type list[],int k,int m) {    
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << list[i];
		}
		cout << endl;
	}

	else {
		for (int i = k; i <= m; i++)
		{
			Swap(int k,int m);
			Perm(list,k+1,m);
			Swap(int k,int m);
		}
	}

}

void Swap(Type &a,Type &b) {
	Type temp = a;
	a = b;
	b = temp;
}