Python递归函数参数问题
Python recursion function parameters issue
我多次调用内部函数来解决子集求和问题,使用所谓的递归解决方案;无论如何,我无法弄清楚为什么 n(这是数组元素的数量)值一开始会减少,直到它达到 0,这是我明白的,但是,在它自身内部再次调用它之后,它使 n 值递增。为什么会这样,因为整个函数甚至没有对 n 值的增量贡献? n 从哪里获得增加的价值?
代码如下:
def printAllSubsetsRec(arr, n, currentSubset, sum):
# If remaining sum is 0, then print all
# elements of current subset.
if (sum == 0):
i = 0
sumOfValue = 0
for value in currentSubset:
i += 1
sumOfValue += value
if (i == len(currentSubset)):
print(value, " = ", sumOfValue)
else:
print(value, end=" + ")
return True
# If there are no elements in the array and the sum is not equal to 0.
if (n == 0 and sum != 0):
return None
# I consider two cases for every element:
# a) Excluding last element.
# b) Including last element in current subset.
# -------------------------------------------------
# Excluding the last element:
printAllSubsetsRec(arr, n - 1, currentSubset, sum)
v = [] + currentSubset
v.append(arr[n - 1])
# Including the last element:
printAllSubsetsRec(arr, n - 1, v, sum - arr[n - 1])
#Main:
arr = [10, 7, 5, 18, 12, 20, 15]
sum = 35
n = len(arr)
currentSubset = []
printAllSubsetsRec(arr, n, currentSubset, sum)
输出应该是:
18 + 7 + 10 = 35
12 + 18 + 5 = 35
20 + 5 + 10 = 35
15 + 20 = 35
提前致谢!
递归是一种函数式继承,因此将它与函数式风格结合使用会产生最佳效果。这意味着要避免突变、变量重新分配和其他副作用 -
- 逻辑
if
没有相应的 else
i
和 sumOfValue
的突变和重新分配
- 类似
print
的副作用
递归不一定是困难或痛苦的。使用功能规则,我们可以用 inductive reasoning -
编写 subsets(t,n)
- 如果目标总和
n
为零,产生空解
- (归纳)否则
n
为负或正。如果 n
为负数或输入数组 t
为空,我们就出界了。停止迭代。
- (inductive)
n
是正数并且 t
至少有一个元素。对于子问题 (t[1:],n-t[0])
的所有 s
,将 t[0]
添加到 s
并产生。 And 产生子问题 (t[1:],n)
的所有结果
def subsets(t, n):
if n == 0:
yield () #1
elif n < 0 or not t:
return #2
else:
for s in subsets(t[1:], n - t[0]): #3
yield (t[0], *s)
yield from subsets(t[1:], n)
for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
print(s)
(10, 7, 18)
(10, 5, 20)
(5, 18, 12)
(20, 15)
通知-
- 所有操作都不会改变或重新分配变量
- 像
print
这样的副作用换来了 yield
- 来电者可以随意使用和转换结果
将结果格式化为数学表达式 -
for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
print(" + ".join(map(str, s)), "=", 35)
10 + 7 + 18 = 35
10 + 5 + 20 = 35
5 + 18 + 12 = 35
20 + 15 = 35
要将生成器的所有输出收集到列表中,请使用 list
-
print(list(subsets([10, 7, 5, 18, 12, 20, 15], 35)))
[(10, 7, 18), (10, 5, 20), (5, 18, 12), (20, 15)]
我多次调用内部函数来解决子集求和问题,使用所谓的递归解决方案;无论如何,我无法弄清楚为什么 n(这是数组元素的数量)值一开始会减少,直到它达到 0,这是我明白的,但是,在它自身内部再次调用它之后,它使 n 值递增。为什么会这样,因为整个函数甚至没有对 n 值的增量贡献? n 从哪里获得增加的价值?
代码如下:
def printAllSubsetsRec(arr, n, currentSubset, sum):
# If remaining sum is 0, then print all
# elements of current subset.
if (sum == 0):
i = 0
sumOfValue = 0
for value in currentSubset:
i += 1
sumOfValue += value
if (i == len(currentSubset)):
print(value, " = ", sumOfValue)
else:
print(value, end=" + ")
return True
# If there are no elements in the array and the sum is not equal to 0.
if (n == 0 and sum != 0):
return None
# I consider two cases for every element:
# a) Excluding last element.
# b) Including last element in current subset.
# -------------------------------------------------
# Excluding the last element:
printAllSubsetsRec(arr, n - 1, currentSubset, sum)
v = [] + currentSubset
v.append(arr[n - 1])
# Including the last element:
printAllSubsetsRec(arr, n - 1, v, sum - arr[n - 1])
#Main:
arr = [10, 7, 5, 18, 12, 20, 15]
sum = 35
n = len(arr)
currentSubset = []
printAllSubsetsRec(arr, n, currentSubset, sum)
输出应该是:
18 + 7 + 10 = 35
12 + 18 + 5 = 35
20 + 5 + 10 = 35
15 + 20 = 35
提前致谢!
递归是一种函数式继承,因此将它与函数式风格结合使用会产生最佳效果。这意味着要避免突变、变量重新分配和其他副作用 -
- 逻辑
if
没有相应的else
i
和sumOfValue
的突变和重新分配
- 类似
print
的副作用
递归不一定是困难或痛苦的。使用功能规则,我们可以用 inductive reasoning -
编写subsets(t,n)
- 如果目标总和
n
为零,产生空解 - (归纳)否则
n
为负或正。如果n
为负数或输入数组t
为空,我们就出界了。停止迭代。 - (inductive)
n
是正数并且t
至少有一个元素。对于子问题(t[1:],n-t[0])
的所有s
,将t[0]
添加到s
并产生。 And 产生子问题(t[1:],n)
的所有结果
def subsets(t, n):
if n == 0:
yield () #1
elif n < 0 or not t:
return #2
else:
for s in subsets(t[1:], n - t[0]): #3
yield (t[0], *s)
yield from subsets(t[1:], n)
for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
print(s)
(10, 7, 18)
(10, 5, 20)
(5, 18, 12)
(20, 15)
通知-
- 所有操作都不会改变或重新分配变量
- 像
print
这样的副作用换来了yield
- 来电者可以随意使用和转换结果
将结果格式化为数学表达式 -
for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
print(" + ".join(map(str, s)), "=", 35)
10 + 7 + 18 = 35
10 + 5 + 20 = 35
5 + 18 + 12 = 35
20 + 15 = 35
要将生成器的所有输出收集到列表中,请使用 list
-
print(list(subsets([10, 7, 5, 18, 12, 20, 15], 35)))
[(10, 7, 18), (10, 5, 20), (5, 18, 12), (20, 15)]