跟郝斌老师复习数据结构part4--专题--递归

一、定义

一个函数自己直接或间接调用自己

#include<stdio.h>
void f(int);
void f(int n){
	if(n==1)	
		printf("哈哈\n");
	else
		f(n-1);
}
int main(void){
	f(3);//哈哈
	return 0;
}

二、递归为什么可以调用自己

2.1直接调用与间接调用

直接调用：

long f(long n){
	if(1==n)
		return 1;
	else
		return f(n-1)*n;
} 

int main(void){
	printf("%ld\n",f(5));//120
	return 0;
}

间接调用：

void f(int n){
	g(n);
}
void g(int m){
	f(m);
}

2.2函数的调用

三、递归需要满足的条件

1. 递归必须得有一个明确的中止条件

2. 该函数所处理的数据规模必须在递减

3. 这个转化必须是可解的

四、举例

2.1求阶乘

long f(long n){
	if(1==n)
		return 1;
	else
		return f(n-1)*n;
} 

int main(void){
	printf("%ld\n",f(5));//120
	return 0;
}

2.2 1+2+3+···+100的和

long sum(long n){
	if(1==n)
		return 1;
	else
		return n+sum(n-1);
} 

int main(void){
	printf("%ld\n",sum(100));//5050
	return 0;
}

2.3汉诺塔