algorithm - 将迭代算法转换为递归算法的问题

Question

我已经很长时间没有研究递归了，所以请耐心等待。

我基本上需要编写一个子例程，如果它们的总和为给定数字，则输出所有数字序列。以下部分显示了一种迭代方法

Sub IterFunc()
    For i = 1 To 5
        For j = 1 To 5
            For k = 1 To 5
                If i + j + k = 4 Then
                    Debug.Print i & ", " & j & ", " & k
                End If
            Next k
        Next j
    Next i
End Sub

如果序列由 3 个整数组成，这会很好地工作，但是它不适用于序列中任意数量的整数。所以需要递归的方法。以下是我尝试重写一个递归版本的子程序

Sub RecuFunc(ByRef tot As Long)
    For i = 1 To 5
        tot = tot + i
        If tot = 5 Then
            Debug.Print i
        ElseIf tot < 5 Then
            Call RecuFunc(tot)
        ElseIf tot > 5 Then
            Call RecuFunc(tot - i)
        End If
    Next i
End Sub

Sub test2()
    Call RecuFunc(0)
End Sub

很快出现了几个问题:a) 我不太确定如何存储序列以在总数匹配时输出它 b) 似乎我需要以某种方式“重置”变量 tot，但我的方法似乎并不奏效。

任何想法都会很棒。如果我的问题很原始，我深表歉意。

谢谢!

Answer 1

这是一个递归函数，给定一个整数 n 和一个目标值 target(假设 > 0)，返回所有字符串的集合形式例如"1 + 2 + 1 + 1"，其中求和中的数字在 1,..., n 范围内，它们求和为目标。集合是一种自然的数据结构，使用字符串的优点是很容易在总和上添加新的术语:

Function IntSums(n As Long, target As Long) As Collection
    Dim sums As New Collection
    Dim partialSums As Collection
    Dim i As Long, m As Long, sum As Variant

    If target = 1 Then
        sums.Add target
        Set IntSums = sums
        Exit Function
    End If
    m = IIf(n < target, n, target) 'm is min(n,target)
    For i = 1 To m
        If i = target Then
            sums.Add Trim(Str(target))
        Else
            Set partialSums = IntSums(n, target - i)
            For Each sum In partialSums
                sums.Add i & " + " & sum
            Next sum
        End If
    Next i
    Set IntSums = sums
End Function

一个测试函数:

Sub test()
    Dim s As Variant, sum As Variant
    Set s = IntSums(5, 5)
    For Each sum In s
        Debug.Print sum
    Next sum
End Sub

输出:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 1 + 3
1 + 2 + 1 + 1
1 + 2 + 2
1 + 3 + 1
1 + 4
2 + 1 + 1 + 1
2 + 1 + 2
2 + 2 + 1
2 + 3
3 + 1 + 1
3 + 2
4 + 1
5