python - 递归树生成器中的无限递归

Question

我的递归python函数有一个有趣的问题我一定是漏掉了一些精巧的底盒什么的！下面代码的目标是构建决策树（用于确定数据趋势的结构）。它是通过嵌套python列表实现的，这就是返回值和结果列表所做的。结构本身并没有那么重要（至少看起来是这样）。

 def tdidt(dataset,attr_list,class_index,class_labels):
    print attr_list

    #base case 1: all the same class
    if all_same_class(dataset, class_index):
        class_label = majority_vote(dataset, class_index)
        return ['c',class_label]
    #base case 2: no more attributes
    elif attr_list == []:
        print 'i see and empty list!!!'
        class_label = majority_vote(dataset, class_index)
        return ['c',class_label]
    else:
        #else select attribute and partition dataset 
        attr = select_attribute(dataset, list(attr_list), class_index, class_labels)
        partitions = partition_on_attr(dataset, attr)

        #base case 3: one of the partitions is empty
        if has_empty_partition(partitions):
            class_label = majority_vote(dataset, class_index)
            return ['c',class_label]
        else:
            #enable respective data attribute labels for easier to read tree
            #result = result + ['a',titanic_header[attr]]
            #result = result + ['a',auto_header[attr]]

            #add attribute node to tree
            result = ['a',attr]
            #remove used attribute
            removed_attr_list = [x for x in list(attr_list) if x != attr]

            for partition in partitions.values():
                #add value node for tree, recursive call for next attributes
                result.append(["v",partition[0][attr],tdidt(partition, list(removed_attr_list), class_index, class_labels)]) 
        return result

attr_list（或与attr_list有关的内容）似乎是最有可能的嫌疑人（请参阅下面的投诉和错误消息）attr_list包含一个属性索引列表，我将通过一次从列表中选择一个属性索引而不进行替换来逐个“使用”。
递归函数的三种基本情况如下：
1（同一类）：
数据集（行列表）中的每一行（属性列表）在按类索引索引的行中共享一个公共值
2（没有更多属性）：
参数属性列表为空这应该是最活跃的基本情况，发生频率最高。
3（分区为空）：
数据在attr（）上按分区分区分区，其中一个分区（行列表）为空，无法继续
递归调用是最长的一行（引起水平滚动条的那一行），函数tdidt（）作为附加列表的一个组件被调用。指定给移除属性列表的列表理解的目的是拥有一个没有我们刚刚从属性列表中选择的属性的属性列表。
好吧，所以我得到的错误是巨大的我达到了递归极限，而且是因为一个非常奇怪的原因我将在函数调用时以及出现空列表时立即打印属性列表。这是输出。。。

[0, 1, 2]
[0, 1]
[1]
[]
i see and empty list!!!
[] 
i see and empty list!!!
[1]
[]
i see and empty list!!!
[]
[1]
[1]
[1]
[1] 
[1]
[1]
.
.
.

强调省略。[1]一直持续到递归最大输出错误。
RuntimeError：CMP中最大递归深度超过
开始的行为正是我所期望的；attr_列表用完了，看到了递归调用上的for循环创建的一些分支，然后基本情况用“我看到了一个空列表！”，然后[1]开始流动！
我遗漏了一个递归的案例吗？如何将attr_列表永久地设置回[1]任何帮助都是非常感谢的，谢谢你使它成为这本小说的底部！
更新日期：2014年10月24日---
在每次递归调用上打印数据集变量时，我看到与attr_list参数类似的行为事情按预期进行，然后数据集参数会一次又一次地变成这一行。。。
[[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”]，[“第三个”，“成人”，“男性”，“无”][“第三个”，“成人”，“男性”，“是”]，[“第三个”，“成人”，“男性”，“否”]，[“第三个”，“成人”，“男性”，“是”]，[“第三个”，“成人”，“男性”，“否”]，[“第三个”，“成人”，“男性”，“否”]，[“第三个”，“男性”，“否”]，[“第三个”，“成人”，“男性”，“否”]，[“第三个”，“成人”，“男性”，“男性”，“否”]，[“第三个”，“第三个”，“成人”，“男性”，“否”][“第三个”，“成人”，“男性”，“没有”]，[“第三个”，“成人”，“男性”，“没有”]，[“第三个”，“成人”，“男性”，“没有”]]
只有一行！（还偷看了一些奇怪的数据）
这到底是怎么回事？这个函数一旦完成它的处理过程，似乎就产生了某种零熔毁除以我的递归一定有问题。
-----------------------------2014年10月25日更新-----------------------------
好吧，我们现在有事情要做。@Njarsson建议在函数partition_on_attr（）返回其接收的同一数据集时检查行为，这意味着所选属性在整个数据集中是一致的，并且不会发生分区。我对这种情况的最初想法是，下一个递归调用将有一个较小的attr_list，并且最终空的attr_list base case将捕获这个分区。很明显我错了，这里有几个我运行过的基本测试用例和它们共享的光…
第一个播放数据集有两个实例，前三个属性是要拆分的属性，第四个是我们试图猜测的属性由于所有分割属性都不相等，因此partition_on_attr（）函数返回整个数据集作为一个分区是不可能发生的。
播放=[[0,0,0,1]，[1,1,1,0]]
输出是一个很棒的决策树（不太美观，但这不是重点）
['a'，0，['v'，0，['c'，1]]，['v'，1，['c'，0]]]
现在让我们尝试一个不同的播放数据集，类似于第一个播放集-两个实例，相同的模式。
播放=[[1,1,1,1]，[1,1,1,0]]
在这个数据集中，前三个属性（要拆分的属性）都是相等的。因此partition_by_attr（）函数必须返回与传递的数据集相同的单个分区出现最大递归错误！
@Njarsson你有什么事！我只是不明白为什么会这样如果partition_on_attr函数将整个数据集作为一个分区返回，算法应该怎么做？

Answer 1

在这段代码中，我没有看到任何单独产生无限递归的东西，我认为问题出在别处。很可能，partition_on_attr生成的分区不严格小于其数据集参数例如，它可能生成一个与参数相等的分区。
我要检查的第一件事是当数据集只有一个元素时partition_on_attr会做什么。它可能返回包含该元素的单个分区，这将产生类似于您的输出。