递归是一个很经典的算法,最常见的就是斐波那契数列,斐波那契数列指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*),最简单的解法就是通过递归:
1
2
3
4
5
6
7
8
|
-(
NSInteger
)simpleRecursive:(
NSInteger
)count{
if
(count==1) {
return
0;
}
else
if
(count==2){
return
1;
}
return
[
self
simpleRecursive:count-1]+[
self
simpleRecursive:count-2];
}
|
通过斐波那契数列可以更清晰理解递归的概念:
必须有可达到的终止条件,否则程序陷入死循环
子问题在规模上比原问题小
子问题可通过再次递归调用求解
子问题的解应能组合成整个问题的解
同样的,我们可以通过递归求解整数的幂,比如说是求解m的n次方:
一般求解m的n次方,一般使用n个m相乘的办法来求解。其实我们还可以使用另外一种更有效率的办法求解这个问题。我们知道一个数的0次方等于1,一个数的1次方等于该数本身。如果一个数的n次方的n可以被2整数,我们可以将求解的问题,分解为m的(n/2)次方乘以m的(n/2)次方。如果不能被2整除,则可以将问题求解转变为m乘以m的(n-1)次方,通过这个递归的办法,我们可以很快的分解求出问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
-(
NSInteger
)power:(
NSInteger
)number count:(
NSInteger
)count{
if
(count==0) {
return
1;
}
if
(count==1) {
return
number;
}
if
(count%2==0) {
return
[
self
power:number*number count:count/2];
}
else
{
return
[
self
power:number*number count:count/2]*number;
}
}
|
循环数组一个数组中的值我们是最常遇到的,如果按顺序输出一个正整数每一位的值我们可以通过递归实现:
1
2
3
4
5
6
|
-(
void
)printOutNumber:(
NSInteger
)number{
if
(number>10) {
[
self
printOutNumber:number/10];
}
NSLog
(@
"数值%ld"
,number%10);
}
|
另外一个经典的场景就是输入字符串abc
,则打印出 a、b、c 所能排列出来的所有字符串 abc
、acb
、bac
、bca
、cab
和 cba
,暴力循环可以得到结果,不过如果这样写出来程序估计日后自己都不想看,这个问题其实是一个全排列的问题,核心的思想就是第一个数字起每个数分别与它后面的数字交换:
如果能生成n-1个元素的全排列,就能生成n个元素的全排列。对于只有一个元素的集合,可以直接生成全排列。所以全排列的递归终止条件很明确,只有一个元素时。我们可以分析一下全排列的过程:
(1)首先,我们固定第一个字符a,求后面两个字符bc的排列
(2)当两个字符bc排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列
(3)将c放在第一个位置,但是记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍是和原先处在第一个位置的a交换,将c和第一个字符交换之前,先要把b和a交换回来。在交换b和a之后,再拿c和处于第一位置的a进行交换,得到cba,交换ba,得到cab。
图片来自网络,如果不清晰可以看下图片:
代码实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
//http://www.cnblogs.com/xiaofeixiang
-(
void
)allRange:(
NSMutableArray
*)arr start:(
NSInteger
)index{
if
(index==arr.count-1)
{
NSString
*result=@
""
;
for
(
NSInteger
i=0; i<arr.count; i++) {
result=[result stringByAppendingString:[arr objectAtIndex:i]];
}
NSLog
(@
"排列:%@"
,result);
}
else
{
for
(
NSInteger
i=index;i<arr.count;i++)
{
//从下标为index的数开始,分别与它后面的数字交换
NSString
*temp=arr[index];
arr[index]=arr[i];
arr[i]=temp;
[
self
allRange:arr start:index+1];
NSString
*tempNext=arr[index];
arr[index]=arr[i];
arr[i]=tempNext;
}
}
}
|
本文转自Fly_Elephant博客园博客,原文链接:http://www.cnblogs.com/xiaofeixiang/p/4535825.html,如需转载请自行联系原作者