了解递归尾递归
2018-09-09 本文已影响0人
Lucky_Man
尾调用概念
尾调用：在计算机学里，尾调用是指一个函数里的最后一个动作(并不是说在函数的最后的位置)是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。[1]此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。[1]尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。
举两个递归相关的例子
一、 斐波那契数列
斐波那契数列指的是这样一个数列 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。
这个数列从第3项开始，每一项都等于前两项之和。
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2(n >= 2)
- 使用代码的形式表示斐波那契数列
/**
返回第num项的斐波那契数列的值
@param num 第num项
@return 第num项的斐波那契数列的值
*/
- (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)];
}
二、 等差数列求和
- 等差数列求和运行环境注意Xcode在Debug模式下和Release模式的不同表现
- 注意尾递归 的优化场景在Xcode为Release模式的时候才会有所体现。
相关代码：
#pragma mark - 递归方式等差数列求和
/**
普通递归方法求首项为1公差为1的等差数列的和
@param num 前num项的等差数列
@return 返回等差数列前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 - 尾递归方式等差数列求和
/**
尾递归的方式求首项为1公差为1的等差数列的和
@param num 前num项
@return 返回等差数列前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
有兴趣的话你也可以看一下相关文章：iOS objc_msgSend尾调用优化机制详解
