尾調(diào)用概念

尾調(diào)用：在計算機學(xué)里饮醇，尾調(diào)用是指一個函數(shù)里的最后一個動作_{(并不是說在函數(shù)的最后的位置)}是返回一個函數(shù)的調(diào)用結(jié)果的情形，即最后一步新調(diào)用的返回值直接被當(dāng)前函數(shù)的返回結(jié)果决记。^[1]此時绪商，該尾部調(diào)用位置被稱為尾位置。尾調(diào)用中有一種重要而特殊的情形叫做尾遞歸讹躯。經(jīng)過適當(dāng)處理囱挑，尾遞歸形式的函數(shù)的運行效率可以被極大地優(yōu)化醉顽。^[1]尾調(diào)用原則上都可以通過簡化函數(shù)調(diào)用棧的結(jié)構(gòu)而獲得性能優(yōu)化（稱為“尾調(diào)用消除”），但是優(yōu)化尾調(diào)用是否方便可行取決于運行環(huán)境對此類優(yōu)化的支持程度如何平挑。

舉兩個遞歸相關(guān)的例子

一游添、 斐波那契數(shù)列

斐波那契數(shù)列指的是這樣一個數(shù)列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233系草，377，610唆涝，987找都，1597，2584廊酣，4181能耻，6765，10946亡驰，17711晓猛，28657，46368
特別指出：第0項是0凡辱，第1項是第一個1戒职。
這個數(shù)列從第3項開始，每一項都等于前兩項之和煞茫。
F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2(n >= 2)

• 使用代碼的形式表示斐波那契數(shù)列

/**
 返回第num項的斐波那契數(shù)列的值

 @param num 第num項
 @return 第num項的斐波那契數(shù)列的值
 */
- (NSUInteger)FibonacciSequenceNum:(NSUInteger)num {
    
    // 0 1 1 2 3 5 8 13
    if (num < 2) {
        return num;
    }
    return [self FibonacciSequenceNum:(num - 1)] + [self FibonacciSequenceNum:(num - 2)];
}

二帕涌、 等差數(shù)列求和

• 等差數(shù)列求和運行環(huán)境注意Xcode在Debug模式下和Release模式的不同表現(xiàn)
• 注意尾遞歸 的優(yōu)化場景在Xcode為Release模式的時候才會有所體現(xiàn)摄凡。
  相關(guān)代碼：

#pragma mark - 遞歸方式等差數(shù)列求和

/**
 普通遞歸方法求首項為1公差為1的等差數(shù)列的和

 @param num 前num項的等差數(shù)列
 @return 返回等差數(shù)列前num項的和
 */
- (NSUInteger)recursiveSumOfArithmeticPropgressionNum:(NSUInteger)num {

    // 1  2  3  4   5   6   7
    // 1  3  6  10  15  21  28
    if (num < 2) {
        return num;
    }
    return [self recursiveSumOfArithmeticPropgressionNum:(num - 1)] + num;
}
#pragma mark - 尾遞歸方式等差數(shù)列求和


/**
 尾遞歸的方式求首項為1公差為1的等差數(shù)列的和

 @param num 前num項
 @return 返回等差數(shù)列前num項的和
 */
- (NSInteger)tailRecursiveSumOfArithmeticProgressionNum:(NSInteger)num {
    
    return [self tailRecurisveNum:num current:0];
}

- (NSInteger)tailRecurisveNum:(NSInteger)num current:(NSInteger)current {
    
    if (num == 0) {
        return current;
    } else {
        return [self tailRecurisveNum:(num - 1) current: (num + current)];
    }
}

我做的一個Demo效果

• Release模式下的效果

  
  
  recursiveTailRecursiveReleaseDemoGif.gif

• Debug模式下的效果

  
  
  recursiveTailRecursiveDebugDemoGif.gif

代碼GitHub地址

有興趣的話你也可以看一下相關(guān)文章：iOS objc_msgSend尾調(diào)用優(yōu)化機制詳解

參考學(xué)習(xí)地址

• 尾調(diào)用
• 尾調(diào)用優(yōu)化
• 尾遞歸
• 尾遞歸
• 斐波那契數(shù)列