python中的迭代与递归

遇到一个情况，需要进行递归操作，但是呢递归次数非常大，有一万多次。先不说一万多次递归，原来的测试代码是java的，没装jdk和编译环境，还是用python吧

先看下原本的java代码：

  public class UpCount {      private long calc(int depth) {          if (depth == 0) return 1;          long cc = calc(depth - 1);          return cc + (depth % 7) + ((((cc ^ depth) % 4) == 0) ? 1 : 0);       }      public static void main(String[] args) {          UpCount uc = new UpCount();          System.out.println(uc.calc(11589));      }  }

java没怎么玩过，但是这几行代码看过来还是没压力的，快刀斩乱麻改为对于python代码

  def calc(depth):      if depth == 0:          return 1      cc = long(calc(depth-1))      xor_mod = (cc ^ depth)%4      if xor_mod == 0:          return cc+(depth%7)+1      else:          return cc+(depth%7)     number = long(calc(11589))  print number

代码粘上去，F5，出错了

这个版本的代码本来是没有加long的，因为之前一串十几位的整数直接拿来就可以用，所以怀疑跟long是不是有关系

当然啦，事实上这里跟long完全没关系，python支持的整数长度可是非常长的，参考之前写的代码如下：

  cimal = 7  original = 28679718602997181072337614380936720482949  array = ""  result= ""  while original !=0:      remainder = original % cimal      array += str(remainder)      original /= cimal  length = len(array)  for i in xrange(0,length):      result += array[length-1-i]  print result

上面这段代码将一串很长的十进制数字转为7进制表示，也可以转为任意进制，换做是8进制和16进制，一个oct(),hex()就搞定了，用辗转相除法来解决吧

因此，可以看出来，出错不在于数的大小，毕竟11589对现在的计算机来说只是小菜，2^16还有65536呢

其实到这里才发现，没有说前面递归报错的真正原因，憔悴了

递归出错的原因是因为python默认的递归限制只有1000次左右，但是这里却要运行10000+，刷了半天：RuntimeError: maximum recursion depth exceeded

于是赶紧查了下，发现可以自己设置递归的限制，见python中递归的最大次数，作为延伸也可以查看官网文档

总的说来就是，为了防止益处和崩溃，python语言默认对次数加了限制，那么我改了这个限制是不是就ok了呢

import sys

# set the maximun depth as 20000

sys.setrecursionlimit(20000)

插入上面代码，果断改20000，这下没这限制应该没问题了，但是结果却大跌眼镜，什么都没输出来，不解了

没有继续查了，问了下小伙伴littlehann，讨论了下， 没有对这个问题深究下去。而是提到递归这种运算在实际应用中的效率，确实除了课本上很少看到使用递归的

本来的目的就只是求值，没想对它深究下去，还是改用迭代吧，虽然没太大印象了，不过一个for语句据可以搞定了

代码如下：

  def calc(depth):      tmp = 0      result = 1            for i in xrange(0,depth+1):          cc = result          if (cc ^ i)%4 == 0:              tmp = 1          else:              tmp = 0          result = result + (i)%7 + tmp                return result  final = calc(11589)  print final

短短几行代码，一下子搞定了。想到上次面试的时候，tx的面试官问我算法，当时提到了用递归实现一个运算，再想想是不是也可以用迭代呢？

时间过去很久了，当时的题目也记不太清楚了，但是今天的教训是：大多数(代码写得少，凭感觉说的估计值)情况下，递归的效率是比较低下的，这一点可以确定，上课的

时候也有讲到过。使用迭代的效率明显要高过递归(迭代的具体概念记不太清楚了)，起码用循环，运算几十万次我可以肯定没问题，但是即便我改了递归限制，还是遇到了罢工

最后，再贴出一个python long VS C long long的链接，感兴趣的可以去看看

• 初学者学习python2还是python3？
• python获取本机IP、mac地址、计算机名
• 详解python2 和 python3的区别
• python基础之删除文件及删除目录的方法
• 用python求第1000个质数的值
• python常用函数年初大总结
• Python3 - 时间处理与定时任务
• Python开发的CMS系统，Silva CMS 3 发布
• python基础之使用os.system来执行系统命令
• 判断python字典中key是否存在的两种方法

• 初学者学习python2还是python3？
• python基础之删除文件及删除目录的方法
• python获取本机IP、mac地址、计算机名
• python获取系统时间（时间函数详解）
• 详解python2 和 python3的区别
• 用python求第1000个质数的值
• Python3 - 时间处理与定时任务
• 命令行看糗百
• Python算法之---冒泡，选择，插入排序算法
• python 中求和函数 sum详解

• range方法在Python2和Python3中的不同
• python3 数组(列表)初始化
• 记一次crontab中date命令错用导致的问题
• MySQL用LIKE特殊字符搜索
• CentOS 7 下修改主机名
• Python3正则表达式之：(?(id/name)y...
• TIOBE编程语言排行榜2019年 Python稳居前三
• 解压命令unzip常用方法汇总
• 解析redis备份文件rdb的两种方法及对比
• 百度视觉语义化平台2.0：交互升级和...
• 5G时代的视觉语义化技术：软硬结合...
• 百度AutoDL重磅升级至3.0：设计、迁...