博客

递归与循环

  • Post author:
  • Post category:其他



原创文章，转载请注明：

转载自

始终不够


本文链接地址:


递归与循环

转载请注明：

始终不够

»

递归与循环

大一学C++的时候，老师说过递归与循环是可以相互转化的，当时好像是用来两重循环解决递归问题，算法的复杂度依然是O(n)。最近发现可以通过模拟实现栈结构通过一重循环实现非递归算法。

递归必须满足以下两个条件：

  • 在每一次调用自己时，必须是（在某种意义上）更接近于解；
  • 必须有一个终止处理或计算的准则。

首先我们给出一个最简单的递归实现，算法的目的是为了得到一个大于等于10的数字。

1
2
3
4
5
6
7

function


recursion(


$data


){



if


(


$data


> 10){



return


$data


;



}



return


recursion(


$data


+ 1);

}

以上代码，当$data <= 10时，调用自己并累加1。

非递归算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function


noRecursion(


$data


){



$result


= null;



$stack


=


new


SplStack();



$stack


->push(


$data


);



do


{



if


(!


$stack


->valid())


break


;



$result


=


$stack


->pop();



if


(


$result


> 10){



return


$result


;



}



$stack


->push(


$result


+ 1);



}


while


(true);



return


$result


;

}

为了保存每次循环产生的中间结果，我们将结果压入一个栈中，等待下次处理。SplStack类为php提供的SPL标准栈结构。

我们知道，递归算法虽然写起来要比用循环来解决问题更加方便，但它所带来的性能问题也是不能忽略的。由于每次递归调用都需要存储本次执行产生的中间结果并压入栈中等待递归返回，对内存和cpu的消耗都非常高。使用模拟栈实现的非递归算法，能够带来本质上的性能提升，且编码并不是非常复杂。原则上推荐在能够使用以上算法实现非递归算法的情况下，尽量少用递归算法。