遞歸是編程語言中一種較為常見的算法，一個函數(shù)直接或間接調(diào)用自身的一種方法俊马。當(dāng)調(diào)用一次函數(shù)可能解決不了當(dāng)前的問題和需求兵怯，需要重復(fù)調(diào)用纵竖，一直到達(dá)成目的兔朦。
常見用法：
（1）對數(shù)組降維，把數(shù)組降成一維
@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）取多層數(shù)組中最里面一層的數(shù)據(jù)
/// 取出來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) {//如果數(shù)組長度為0或1時(shí)返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大，繼續(xù)查找
j--;
}
//如果比基準(zhǔn)數(shù)小声邦，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當(dāng)在右邊查找到一個比基準(zhǔn)數(shù)小的值時(shí)乏奥，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準(zhǔn)數(shù)小，繼續(xù)查找
i++;
}
//如果比基準(zhǔn)數(shù)大亥曹，則將查找到的大值調(diào)換到j(luò)的位置
array[j] = array[i];
}
//將基準(zhǔn)數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
NSLog(@"before--left%d---%d",i,rightIndex);
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準(zhǔn)數(shù)右邊的
NSLog(@"afterleft---%d---%d",i,rightIndex);
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
（4）二叉樹的創(chuàng)建：
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塊錢能買多少瓶酒骗炉？
遞歸算法解決
/**
* 計(jì)算酒瓶數(shù)
* @param beer 啤酒數(shù)
* @param bottleCaps 瓶蓋數(shù)
* @param bottle 瓶子數(shù)
*/
- (void)calculateBeerWithBeer:(int)beer bottleCaps:(int)bottleCaps bottle:(int)bottle{
NSLog(@"第%d次的啤酒數(shù):%d,瓶蓋數(shù):%d,瓶子數(shù):%d",self.i,beer,bottleCaps,bottle);
/** 不管什么，反正瓶蓋和瓶子等于啤酒（可能有換不完的） */
bottle += beer;
bottleCaps += beer;
/** 換完瓶蓋和瓶子之后的啤酒數(shù)蛇受，瓶蓋數(shù)句葵，瓶子數(shù) */
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.
}
