iOS之递归算法

递归是编程语言中一种较为常见的算法，一个函数直接或间接调用自身的一种方法。当调用一次函数可能解决不了当前的问题和需求，需要重复调用，一直到达成目的。
常见用法：
（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.
}