标签: recursion

背景:我正在使用最小构造算法构建一个代表字典的trie.输入列表是4.3M utf-8字符串,按字典顺序排序.生成的图形是非循环的,最大深度为638个节点.我的脚本的第一行将递归限制设置为1100 sys.setrecursionlimit().

问题:我希望能够将我的trie序列化到磁盘,因此我可以将其加载到内存中而无需从头开始重建(大约22分钟).我曾经尝试都pickle.dump()和cPickle.dump(),用文本和二进制协议两种.每次,我得到一个如下所示的堆栈跟踪:

  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 649, in save_dict
    self._batch_setitems(obj.iteritems())
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 663, in _batch_setitems
    save(v)
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 725, in save_inst
    save(stuff)
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 648, in save_dict
    self.memoize(obj)
RuntimeError: maximum recursion depth exceeded

我的数据结构相对简单: trie包含对开始状态的引用,并定义了一些方法. dfa_state包含布尔字段,字符串字段和从标签到状态的字典映射.

我对内部工作原理并不十分熟悉pickle- …

嘿大家好,我正在努力简化我的一个作业问题并使代码更好一些.我正在使用的是二叉搜索树.现在我在我的Tree()类中有一个函数,它找到所有元素并将它们放入列表中.

tree = Tree()
#insert a bunch of items into tree

然后我使用我的makeList()函数从树中获取所有节点并将它们放在一个列表中.makeList()我打电话给这个功能tree.makeList(tree.root).对我来说,这似乎有点重复.我已经调用了树对象,tree.所以这tree.root只是浪费一点点打字.

现在makeList函数是:

    def makeList(self, aNode):
        if aNode is None:
            return []
        return [aNode.data] + self.makeList(aNode.lChild) + self.makeList(aNode.rChild)

我想让aNode输入一个默认参数,例如aNode = self.root(这不起作用),这样我可以运行这个函数,tree.makeList().

第一个问题是,为什么不起作用？
第二个问题是,有没有办法可以运作？正如你所看到的那样,makeList()函数是递归的,所以我无法在函数的开头定义任何东西,或者我得到一个无限循环.

编辑 以下是所有要求的代码:

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self):
        self.root = None

    def __str__(self):
        current = self.root

    def isEmpty(self):
        if …

我正在尝试对给定路径下的所有文件执行某些操作.我不想事先收集所有的文件名然后用它们做一些事情,所以我尝试了这个:

import os
import stat

def explore(p):
  s = ''
  list = os.listdir(p)
  for a in list:
    path = p + '/' + a
    stat_info = os.lstat(path )
    if stat.S_ISDIR(stat_info.st_mode):
     explore(path)
    else:
      yield path

if __name__ == "__main__":
  for x in explore('.'):
    print '-->', x

但是这个代码在命中它们时会跳过目录,而不是让它们产生内容.我究竟做错了什么？

我一直试图Tail call optimization在JavaScript的上下文中理解并编写了下面的递归和尾递归方法factorial().

递归:

function factorial (n) {
  if (n < 2) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

尾递归:

function factorial (n) {
  function fact(n, acc) {
    if (n < 2) {
      return acc;
    } else {
      return fact(n-1, n * acc);
    }
  }

  return fact(n, 1)
}

但我不确定tail-recursive该函数的版本是否会被JavaScript编译器优化,因为它是在Scala等其他语言中完成的.有人可以帮我解决这个问题吗？

我一直在学习 C++constexpr函数，我实现了一个constexpr递归函数来找到第 n 个斐波那契数。

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

constexpr long long fibonacci(int num) {
    if (num <= 2) return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
    auto start = clock();
    long long num = fibonacci(70);
    auto duration = (clock() - start) / (CLOCKS_PER_SEC / 1000.);
    std::cout << num << "\n" << duration << std::endl;
}

如果我constexpr从fibonacci()函数中删除标识符，则fibonacci(70)需要很长时间来评估（超过 …

有没有一种方法可以在Javascript中定义一个函数并立即调用它,以一种允许它重用的方式？

我知道你可以做一次性的匿名功能:

(function(i) {
    var product = i * i;
    console.log(product);
    // Can't recurse here because there's no (ECMA standard) way for the 
    // function to refer to itself
}(2)); // logs 4

或者你可以命名一个函数然后调用它:

function powers(i) {
    var product = i * i;
    console.log(i * i);
    if (product < 1e6) { powers(product) };
}

powers(2); // Logs 4, 16, 256...

但是,有一种更清晰的方法可以一次性定义和调用函数吗？有点像两个例子的混合？

不能做到这一点并不妨碍我做任何事情,但感觉它是一种很好的表达方式来编写需要运行的递归函数或函数,$(document).ready()但稍后当情况发生变化时等等.

我有一个扁平的字典,我想把它变成一个嵌套的字典

flat = {'X_a_one': 10,
        'X_a_two': 20, 
        'X_b_one': 10,
        'X_b_two': 20, 
        'Y_a_one': 10,
        'Y_a_two': 20,
        'Y_b_one': 10,
        'Y_b_two': 20}

我想将其转换为表单

nested = {'X': {'a': {'one': 10,
                      'two': 20}, 
                'b': {'one': 10,
                      'two': 20}}, 
          'Y': {'a': {'one': 10,
                      'two': 20},
                'b': {'one': 10,
                      'two': 20}}}

扁平字典的结构使得模糊不应存在任何问题.我希望它适用于任意深度的字典,但性能并不是真正的问题.我已经看到很多用于展平嵌套字典的方法,但基本上没有用于嵌套扁平字典的方法.存储在字典中的值是标量或字符串,永远不会迭代.

到目前为止,我有一些可以接受输入的东西

test_dict = {'X_a_one': '10',
             'X_b_one': '10',
             'X_c_one': '10'}

到输出

test_out = {'X': {'a_one': '10', 
                  'b_one': '10', 
                  'c_one': '10'}}

使用代码

def nest_once(inp_dict):
    out = {}
    if isinstance(inp_dict, dict):
        for key, val in inp_dict.items():
            if '_' …

有什么控制可以递归调用一些东西吗？

从一个基本的测试程序,我得到一个超过18k的递归深度

这取决于stacksize ....

有没有办法设置一个大块的内存(也许是一个线程)与大量的堆栈,以增加递归深度？

为了估计最大调用深度,递归方法可以用给定量的存储器实现,在堆栈溢出错误可能发生之前计算所用存储器的(近似)公式是什么？

编辑:

许多人回答"它依赖",这是合理的,所以让我们通过使用一个微不足道但具体的例子来删除一些变量:

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

很容易证明,在我的Eclipse IDE中运行它会爆炸n不到1000(对我来说非常低).这个调用深度限制是否可以在不执行的情况下估算？

编辑:我不禁认为Eclipse有一个固定的最大调用深度1000,因为我得到了998,但是有一个用于main,一个用于初始调用方法,1000总而言之.这是一个"太圆"的数字恕我直言,是一个巧合.我会进一步调查.我只是Dux开销-Xss vm参数; 它是最大的堆栈大小,所以Eclipse运行器必须-Xss1000设置在某处

我尝试计算Ackermann(4,1),不同语言/编译器之间的性能差异很大.以下是我的Core i7 3820QM,16G,Ubuntu 12.10 64bit的结果,

C:1.6s,gcc -O3 (gcc 4.7.2)

int ack(int m, int n) {
  if (m == 0) return n+1;
  if (n == 0) return ack(m-1, 1);
  return ack(m-1, ack(m, n-1));
}

int main() {
  printf("%d\n", ack(4,1));
  return 0;
}

OCaml:3.6s,ocamlopt (与ocaml 3.12.1)

let rec ack = function
  | 0,n -> n+1
  | m,0 -> ack (m-1, 1)
  | m,n -> ack (m-1, ack (m, n-1))
in print_int (ack (4, 1)) …