首页 > 试题广场 > 对递归程序的优化的一般的手段为()
[单选题]

对递归程序的优化的一般的手段为()

  • 尾递归优化
  • 循环优化
  • 堆栈优化
  • 停止值优化

4个回答

添加回答
A、B
常见的优化手段有尾递归迭代循环
尾递归在每一次递归的过程中保持了上一次计算的状态,也就是“线性迭代过程”
尾递归和一般的递归不同在对内存的占用,普通递归创建stack累积而后计算收缩,尾递归只会占用恒量的内存(和迭代一样)

举一个简单的例子:
//尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。
string story() { 从前有座山,山上有座庙,庙里有个老和尚,
    一天老和尚对小和尚讲故事:story() } 
 
//非尾递归,下一个函数结束以后此函数还有后续,
//所以必须保存本身的环境以供处理返回值。  
string story() {
    从前有座山,山上有座庙,庙里有个老和尚,
    一天老和尚对小和尚讲故事:story(),
    小和尚听了,觉得还是上牛客网刷题靠谱 。 }

编辑于 2017-01-12 14:27:00 回复(2)
A  尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。 尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。 遗憾的是,大多数编程语言没有针对尾递归做优化,
发表于 2017-01-12 14:52:58 回复(0)
以斐波那契数列为例子
普通的递归版本
int fab(int n){
    if(n<3)
        return 1;
    else
        return fab(n-1)+fab(n-2);  
}

具有"线性迭代过程"特性的递归---尾递归过程
int fab(int n,int b1=1,int b2=1,int c=3){
    if(n<3)
        return 1;
    else {
        if(n==c)
             return b1+b2;
        else
             return fab1(n,b2,b1+b2,c+1);
    }
}
以fab(4)为例子
普通递归fab(4)=fab(3)+fab(2)=fab(2)+fab(1)+fab(2)=3  6次调用
尾递归fab(4,1,1,3)=fab(4,1,2,4)=1+2=3                         2次调用
编辑于 2017-05-23 15:22:04 回复(2)
a
发表于 2017-01-12 13:15:04 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋