递归是编程语言中一种较为常见的算法，一个函数直接或间接调用自身的一种方法。当调用一次函数可能解决不了当前的问题和需求，需要重复调用，一直到达成目的。
常见用法：
（1）对数组降维，把数组降成一维
@interface ViewController ()
@property(nonatomic,strong)NSMutableArray *tmpArray;
@end
#pragma mark -- 递归
-(NSMutableArray *)outputArray:(NSArray *)mutArray
{
for (int i = 0;i< mutArray.count ; i++) {
if ([mutArray[i] isKindOfClass:[NSArray class]]) {
[self outputArray:mutArray[i]];
}else{
NSLog(@"");
[_tmpArray addObject:mutArray[i]];
}
}
return _tmpArray;
}
- (void)viewDidLoad {
[super viewDidLoad];
_tmpArray =[[NSMutableArray alloc]init];
NSArray *testArray = @[@"2",@3,@[@"re",@"fd"],@[@"rr",@"ll",@[@[@8,@"fd"],@"jj"]]];
NSMutableArray *resultArray = [self outputArray:testArray];
NSLog(@"%@",resultArray);
}
2020-11-04 18:41:22.700030+0800 id[919:24985] (
2,
3,
re,
fd,
rr,
ll,
8,
fd,
jj
)
（2）取多层数组中最里面一层的数据
/// 取出来fatherTagList中tagList为空的weight值。
let fatherTagList = [
[
"weight": 0,
"tagList": [],
],
[
"weight": 1,
"tagList": [["weight": 2,"tagList": []]]
],
[
"weight": 3,
"tagList": [["weight": 4,"tagList": [["weight": 5,"tagList": []]]]]
],
]
print(recursiveFunc(array: fatherTagList))
//[0, 2, 5]
func recursiveFunc(array: Array<Any>) -> Array<Any> {
for (_, value) in array.enumerated() {
let valueTemp = value as? [String: Any] ?? [:]
let tagList = valueTemp["tagList"] as? Array<Any> ?? []
if tagList.count == 0 {
if let weight = valueTemp["weight"] as? Int {
resultArray.append(weight)
}
} else {
recursiveFunc(array: tagList)
}
}
return resultArray
}
（3）算法之快排
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
// NSLog(@"%@---%d---%d",array,leftIndex,rightIndex);
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
NSLog(@"before--left%d---%d",i,rightIndex);
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
NSLog(@"afterleft---%d---%d",i,rightIndex);
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
（4）二叉树的创建：
class func createBinaryTree(value:Int , treeModel:BinaryTree) {
if treeModel.value <= 0 {
treeModel.value = value
return
}
let midValue = treeModel.value
if value < midValue {
if (treeModel.leftTree == nil){
treeModel.leftTree = BinaryTree()
treeModel.leftTree?.value = value
return
}else{
createBinaryTree(value: value, treeModel: treeModel.leftTree!)
}
}else{
if (treeModel.rightTree == nil){
treeModel.rightTree = BinaryTree()
treeModel.rightTree?.value = value
return
}else{
createBinaryTree(value: value, treeModel: treeModel.rightTree!)
}
}
}
（5）面试题之递归
题目：10块钱买5瓶酒，2个瓶盖换一瓶，4个酒瓶换一瓶。问10块钱能买多少瓶酒？
递归算法解决
/**
* 计算酒瓶数
* @param beer 啤酒数
* @param bottleCaps 瓶盖数
* @param bottle 瓶子数
*/
- (void)calculateBeerWithBeer:(int)beer bottleCaps:(int)bottleCaps bottle:(int)bottle{
NSLog(@"第%d次的啤酒数:%d,瓶盖数:%d,瓶子数:%d",self.i,beer,bottleCaps,bottle);
/** 不管什么，反正瓶盖和瓶子等于啤酒（可能有换不完的） */
bottle += beer;
bottleCaps += beer;
/** 换完瓶盖和瓶子之后的啤酒数，瓶盖数，瓶子数 */
beer = bottleCaps / 2 + bottle / 4;
bottleCaps = bottleCaps % 2;
bottle = bottle % 4;
NSLog(@"最后一共喝了:%d瓶啤酒",self.number += beer);
if (beer == 0) return ;
self.i ++;
[self calculateBeerWithBeer:beer bottleCaps:bottleCaps bottle:bottle];
}
@interface ViewController ()
@property (nonatomic ,assign) int i;
@property (nonatomic ,assign) int number;
@end
- (void)viewDidLoad {
[super viewDidLoad];
self.i = 1;
self.number = 5;
[self calculateBeerWithBeer:5 bottleCaps:0 bottle:0];
// Do any additional setup after loading the view.
}
