过程代码中的递归函数与 SQL

Question

我想知道以下递归代码示例的翻译（这里是 Python，但语言并不重要）在 SQL 中是否大致正确：

def countdown(num):
    if num > 0:
        return countdown(num-1)
    else:
        return num

现在，它没有任何“输出”，因此为了使其与 SQL 行类似，我为每个“结果”返回一个数组：

res = []
def countdown(num):
    res.append(num)
    if num > 0:
        return countdown(num-1)
    else:
        return res

res = countdown(4)
# [4, 3, 2, 1, 0]

这是我在 SQL 中的尝试：

WITH RECURSIVE countdown AS 
(
    SELECT 4 AS num
    UNION ALL
    SELECT num-1 FROM countdown WHERE num > 0
)
SELECT num 
FROM countdown;

 num 
-----
   4
   3
   2
   1
   0

这个翻译准确吗？对于 SQL 实现，我觉得有些“奇怪”的事情：

• 这里的“参数”（n=4）需要硬编码在CTE内部。有没有其他方法可以解决这个问题，使其读起来更像“正常递归函数”？我几乎在期待像

  SELECT num FROM countdown(4)

  这样的事情。
• 基本条件使事情开始，而过程函数中的基本条件“结束事情”。这样的理解正确吗？

• WHERE

  条件本质上对基本条件（

  num > 0

  ）进行编码。

这是正确的理解吗？

Answer 1

我不知道这是否有帮助，但这里是对递归 SQL 可能执行的操作的（合理的）过程解释：

def extend_cur_set_to_new_set(cur_set):
    cur_values = list(cur_set)
    new_values = [ (i - 1) for i in cur_values if i > 0 ]
    return set(new_values + cur_values)

def countdown_find_fixpoint(cur_set):
    print(f"countdown_find_fixpoint({cur_set})")
    new_set = extend_cur_set_to_new_set(cur_set)
    print(f"{cur_set} has been extended to {new_set}")
    if cur_set == new_set:
        print("Fixpoint reached")
        return cur_set
    else:
        return countdown_find_fixpoint(cur_set | new_set)

print(countdown_find_fixpoint({4}))

当上面运行时：

countdown_find_fixpoint({4})
{4} has been extended to {3, 4}
countdown_find_fixpoint({3, 4})
{3, 4} has been extended to {2, 3, 4}
countdown_find_fixpoint({2, 3, 4})
{2, 3, 4} has been extended to {1, 2, 3, 4}
countdown_find_fixpoint({1, 2, 3, 4})
{1, 2, 3, 4} has been extended to {0, 1, 2, 3, 4}
countdown_find_fixpoint({0, 1, 2, 3, 4})
{0, 1, 2, 3, 4} has been extended to {0, 1, 2, 3, 4}
Fixpoint reached
{0, 1, 2, 3, 4}

4

不是一个参数，它是初始集合

{4}

，它将一直增长直到获得固定点（即，如果增长，会产生自身的集合）。到那时我们就完成了。

这与增长最初为空的列表（或集合）直到达到停止条件（即所有所需元素都在列表（或集合）中）为止完全不同。这可以根据口味使用循环或递归下降（尾递归或非尾递归）来编写。在Python中，人们宁愿使用循环，因为保存结果的列表是可变的，并且人们可以自由地

insert()

进入它并

append()

到它。

附注

在具有不可变数据结构的语言中，我们会编写递归下降（这里，如果删除

print()

指令，则为尾递归），如下所示：

def countdown_tailrec_help(cur,list):
    if cur >= 0:
        newlist = list.copy()
        newlist.append(cur)
        print(f"Calling countdown_tailrec_helper({cur-1}, {newlist})")
        res = countdown_tailrec_help(cur-1, newlist)
    else:
        res = list
    print(f"countdown_tailrec_help({cur},{list}) returns {res}")
    return res

def countdown_tailrec(num):
    print(f"Calling countdown_tailrec_helper({num}, [])")
    return countdown_tailrec_help(num,[])

print(countdown_tailrec(4))

然后：

Calling countdown_tailrec_helper(4, [])
Calling countdown_tailrec_helper(3, [4])
Calling countdown_tailrec_helper(2, [4, 3])
Calling countdown_tailrec_helper(1, [4, 3, 2])
Calling countdown_tailrec_helper(0, [4, 3, 2, 1])
Calling countdown_tailrec_helper(-1, [4, 3, 2, 1, 0])
countdown_tailrec_help(-1,[4, 3, 2, 1, 0]) returns [4, 3, 2, 1, 0]
countdown_tailrec_help(0,[4, 3, 2, 1]) returns [4, 3, 2, 1, 0]
countdown_tailrec_help(1,[4, 3, 2]) returns [4, 3, 2, 1, 0]
countdown_tailrec_help(2,[4, 3]) returns [4, 3, 2, 1, 0]
countdown_tailrec_help(3,[4]) returns [4, 3, 2, 1, 0]
countdown_tailrec_help(4,[]) returns [4, 3, 2, 1, 0]
[4, 3, 2, 1, 0]