Iterative vs. Recursive Approaches

Eyal Lantzman, 5 Nov 2007 CPOL
 
     
 
 

Introduction

This article was originally posted at blogs.microsoft.co.il/blogs/Eyal.

Recursive function – is a function that is partially defined by itself and consists of some simple case with a known answer. Example: Fibonacci number sequence, factorial function, quick sort and more.
Some of the algorithms/functions can be represented in an iterative way and some may not.

Iterative
functions – are loop based imperative repetitions of a process (in
contrast to recursion which has a more declarative approach).

Comparison between Iterative and Recursive Approaches from Performance Considerations

Factorial

Collapse | Copy Code
//recursive function calculates n!
static int FactorialRecursive(int n)
{
if (n <= 1) return 1;
return n * FactorialRecursive(n - 1);
} //iterative function calculates n!
static int FactorialIterative(int n)
{
int sum = 1;
if (n <= 1) return sum;
while (n > 1)
{
sum *= n;
n--;
}
return sum;
}
N Recursive Iterative
10 334 ticks 11 ticks
100 846 ticks 23 ticks
1000 3368 ticks 110 ticks
10000 9990 ticks 975 ticks
100000 stack overflow 9767 ticks

As we can clearly see, the recursive is a lot slower than the iterative (considerably) and limiting (stackoverflow).

The reason for the poor performance is heavy push-pop of the registers in the ill level of each recursive call.

Fibonacci

Collapse | Copy Code
//--------------- iterative version ---------------------
static int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1; int prevPrev = 0;
int prev = 1;
int result = 0; for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
} //--------------- naive recursive version ---------------------
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1; return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
} //--------------- optimized recursive version ---------------------
static Dictionary<int> resultHistory = new Dictionary<int>(); static int FibonacciRecursiveOpt(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (resultHistory.ContainsKey(n))
return resultHistory[n]; int result = FibonacciRecursiveOpt(n - 1) + FibonacciRecursiveOpt(n - 2);
resultHistory[n] = result; return result;
}
N Recursive Recursive opt. Iterative
5 5 ticks 22 ticks 9 ticks
10 36 ticks 49 ticks 10 ticks
20 2315 ticks 61 ticks 10 ticks
30 180254 ticks 65 ticks 10 ticks
100 too long/stack overflow 158 ticks 11 ticks
1000 too long/stack overflow 1470 ticks 27 ticks
10000 too long/stack overflow 13873 ticks 190 ticks
100000 too long/stack overflow too long/stack overflow 3952 ticks

As before, the recursive approach is worse than iterative however, we could apply memorizationpattern (saving previous results in dictionary for quick key based access), although this pattern isn't a match for the iterative approach (but definitely an improvement over the simple recursion).

Notes

  1. The calculations may be wrong in big numbers, however the algorithms should be correct.
  2. For timer calculations, I used System.Diagnostics.Stopwatch.

Points of Interest

  1. Try not to use recursion in system critical locations.
  2. Elegant solutions not always the best performing when used in "recursive situations".
  3. If you required to use recursion, at least try to optimize it with dynamic programming approaches (such as memorization).

转自:http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches

关于Tail Recursive

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

I would write the algorithm in the way that makes the most sense and is the most clear for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

转自: http://stackoverflow.com/questions/72209/recursion-or-iteration

参考资料:

尾调用:

http://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

http://en.wikipedia.org/wiki/Tail_call

最新文章

  1. ES6之const命令
  2. iOS中的一些细节
  3. __new__静态方法
  4. Configuring Autofac to work with the ASP.NET Identity Framework in MVC 5
  5. 栈的理解以及如何计算程序所需栈的大小并在IAR中设置栈
  6. NOIP2016日记
  7. Nopcommerce 二次开发1 基础
  8. vba 笔记
  9. apache 配置https
  10. 第43讲:Scala中类型变量Bounds代码实战及其在Spark中的应用源码解析
  11. with(nolock)的用法
  12. jQuery实现一个全选复选框联动效果
  13. DECLARE CONTINUE HANDLER FOR NOT FOUND
  14. javascript 计算中文字符长度
  15. libgdx如何调用android平台内容
  16. node(基础)_node.js中的http服务以及模板引擎的渲染
  17. java执行post请求,并获取json结果组成想要的内容存放本地txt中
  18. IntelliJ IDEA(Ultimate版本)的下载、安装和WordCount的初步使用(本地模式和集群模式)
  19. 微信小程序封装storage(含错误处理)
  20. 【free() invalid next size】谨慎地在C++的类中存储指针来方便访问其他节点

热门文章

  1. 在命令行上 使用 mutt, fetchmail, maildrop, msmtp 收发邮件
  2. 源码安装和配置zabbix 3.0 LST
  3. eclipse could not create the Java Vitual Machine
  4. DB2保存图片并读取动态显示图片
  5. windows2003密码忘记了该如何处理
  6. linux上传下载文件rz,sz
  7. ubuntu(14.4) 安装phpmyadmin
  8. 基于HTTP在互联网传输敏感数据的消息摘要、签名与加密方案
  9. 什么是Asterisk,它如何帮助我们的呼叫中心?
  10. RHEL7 -- systemd