基于While循环的递归函数转换：BOM数据层级计算代码改写

问题描述 #

现有BOM结构的数据框，已通过While循环实现从顶层（level 0）到底层的物料层级定义，要求将该逻辑转换为递归函数实现，不使用data tree类工具。

原始BOM数据 #

df2 <- structure(list(product_id = c("P1", "P1", "P1", "P1", "P1", "P1", 
"P1", "P1", "P1", "P2", "P2", "P2", "P2", "P2", "P2", "P2", "P2", 
"P2"), item_id = c("i1", "i2", "i3", "i4", "i5", "i6", "i7", 
"i8", "i9", "i10", "i11", "i12", "i13", "i14", "i15", "i16", 
"i17", "i18"), sup_item_id = c("i6", "i6", "i6", "i6", "i8", 
"i8", "i9", "i9", NA, "i15", "i15", "i15", "i15", "i17", "i17", 
"i18", "i18", NA), quantity = c(2, 2, 5, 1, 1, 2, 4, 1, 1, 2, 
2, 5, 1, 1, 2, 4, 1, 1), price = c(2, 5, 3, 7, 10, 0, 4, 0, 0, 
2, 5, 3, 7, 20, 0, 2, 0, 0), itemtype = c("A", "A", "A", "A", 
"A", "B", "A", "B", "C", "A", "A", "A", "A", "A", "B", "A", "B", 
"C")), class = "data.frame", row.names = c(NA, -18L))

原While循环实现代码 #

df2 <- df2 %>%
    arrange(product_id, item_id) %>%
    mutate(production_level = ifelse(is.na(sup_item_id), 0, 1))
idx <- which(df2$production_level == 1)
changed <- TRUE
while (changed) {
    changed <- FALSE
    for (i in idx) {
        descendants <- which(df2$sup_item_id == df2$item_id[i])
        if (length(descendants) > 0) {
            new_levels <- df2$production_level[i] + 1
            if (any(df2$production_level[descendants] < new_levels)) {
                df2$production_level[descendants] <- new_levels
                changed <- TRUE
            }
        }
    }
}

递归函数实现 #

递归思路：从顶层节点（level 0）出发，递归遍历其所有子节点，为每个子节点设置层级为父节点层级+1，再继续处理子节点的子节点，直到没有子节点为止。

递归函数定义 #

calculate_bom_levels <- function(df) {
    # 初始化层级：顶层节点（sup_item_id为NA）设为0，其余先设为NA
    df <- df %>%
        arrange(product_id, item_id) %>%
        mutate(production_level = ifelse(is.na(sup_item_id), 0, NA_integer_))
    
    # 递归处理节点的子节点
    process_children <- function(parent_id, parent_level) {
        # 找到当前父节点的所有子节点
        child_indices <- which(df$sup_item_id == parent_id)
        if (length(child_indices) == 0) {
            return()
        }
        # 设置子节点的层级
        df$production_level[child_indices] <<- parent_level + 1
        # 递归处理每个子节点的子节点
        for (child_id in df$item_id[child_indices]) {
            process_children(child_id, parent_level + 1)
        }
    }
    
    # 遍历所有顶层节点，启动递归
    top_level_ids <- df$item_id[which(is.na(df$sup_item_id))]
    for (top_id in top_level_ids) {
        process_children(top_id, 0)
    }
    
    return(df)
}

调用方式 #

# 应用递归函数
df2_with_levels <- calculate_bom_levels(df2)

# 查看结果
print(df2_with_levels)

说明 #

• 该递归函数从顶层节点开始，逐层向下遍历所有子节点，确保每个节点的层级正确继承父节点层级+1
• 使用<<-赋值符修改外部函数中的数据框，确保递归过程中层级更新能被保留
• 逻辑与原While循环完全一致，但通过递归避免了循环迭代的判断逻辑

内容的提问来源于stack exchange，提问作者LHA