递归
1.易于描述和理解，证明简单； 2.在动态规划、贪心算法、回溯法等中有应用； 3.需要注意的是 （1）子问题必须和原问题是相同性质，不然就无法再继续递归调下去了； （2）递归调用必须有一个结束的条件，否则递归调用就无法结束了；
例题：
一、递归求幂；
核心代码：
if
(m
==0
)
return 1；
y
=power
(x,m/2
);
y
=y*y
;
if
(m%2
!=0
)
y
=y*x
完整代码：
double power
(double x,int n
);
int main
()
{
int n
;
double x,y
;
printf
("依次输入实数基数和整数次幂\n");
scanf
("%lf %d",
&x,
&n
);
y
=power
(x,n
);
printf
("power(%lf,%d) = %lf",x,n,y
);//此时的power不做函数；
return 0
;
}
double power
(double x,int m
)//返回值为double所以函数开头用double；
{
double y
;
if
(m
==0
)
return 1
;//?做递归最后的终止
y
=power
(x,m/2
);//此处m为int类型 每次递归都会使m除2 直到m
=0；（这里插一句int类型中3/2
=1 -_-
!）
;
y
=y*y
;
if
(m%2
!=0
)
y
=y*x
;
return y
;
}
样例输入：0.9 100 样例输出：0.000027
样例输入：1.1 100 样例输出：13780.612340
每天多学0.1: 加油！（-。-）
二、求连通区域的面积；
"@"表示可以连通区域；"#"表示阻塞区域； 3.其中阻塞区域“#”在随机位置生成，且生成随机个； 完整代码：
int x1
;
int y1
;
char str
[N
][N
];
int Hsuiji
();
int Lsuiji
();
void output
();
int digui
(int n,int m
) ;
int main
()
{
int i,j,z
;
printf
("迷宫行列\n");
scanf
("%d %d",
&x1,
&y1
);
for
(i
=0
;i
<x1
;i++
)
{
for
(j
=0
;j
<y1
;j++
)
str
[i
][j
]='@';
}
srand
((unsigned int)time(NULL));
srand
(time
(NULL
));
for
(i
=0
;i
<Lsuiji
();i++
)
str
[Lsuiji
()][Lsuiji
()]='#';//随机生成“
output
();//输出；
z
=digui
(0,0
);
printf
("\n");
printf
("%d\n",z
);
output
();
return 0
;
}
int Lsuiji
()//列数最大
{
return rand
()%10+1
;//zai 1~10之间生成随机数；
}
void output
()
{
int i ,j
;
for
(i
=0
;i
<x1
;i++
)
{
for
(j
=0
;j
<y1
;j++
)
printf
("%c",str
[i
][j
]);
printf
("\n");
}
}
int digui
(int x,int y
)
{
if
(x
<0
||y
<0
||x
>x1-1
||y
>y1-1
)
return 0
;
if
(str
[x
][y
]=='#')
return 0
;
str
[x
][y
]='#';//将加过的位置赋值为
"#",避免重复加；若没有这句就会无限循环
return 1+digui
(x+1,y
)+digui
(x-1,y
)+digui
(x,y+1
)+digui
(x,y-1
);
//这里控制x y向上下左右四个方向衍生。
}
样例输入： 2 3 样例输出： @@@ @@@ 6 样例输入： 10 10 样例输出： @@@@@@@@#@ @@@@@@@@@# @@@@@@@@@@ @@@@@@@@@@ @@@@@@@@@@ @@@@@@@@@@ @@@#@@@@@@ @#@@@@@@@@ @@@@@@@@@@ @@@@@@@@@@ 95
