在python中如何用用递归

在python中，如何运用递归的方法来解决。给定一个数字“a”和一个素数列表“blist” (按升序排列），找到一个使用一些blist 中加起来为“a”的数字组合。例如，如果 a = 17 且 blist = [2, 3, 5]，则总和为2+5+5+5 = 17blist 中加起来为 'a' 的数字组合则为true，如果不存在，则为 False。例如, a=9 blist= [5, 6], 则总和加起来没办法是9，所以返回为False。

并且使用函数应返回数字总和的表达式从 blist 以列表的形式加起来为 'a'。如果不存在总和，则返回一个空列表[ ]。

运用递归函数

        def sum_ex( a, i=0 blist)#用来验证True 和False

        def find_s(a, i = 0, blist, slist)
        #用来验证加法的过程，例如a = 17 且 blist = [2, 3, 5]如果存在总和，return[2,2,2,2,2,2,2,3] 或是a=9 blist= [5, 6] 不存在总和，会 return [ ]

结题思路：
递归求和 n = int(input()) jie = 1 sum = 0 i = 1 while n >= i: jie = jie * i sum = sum + jie i = i + 1 print(sum)
当所有 list[i]都小于等于 list[i+1]才返回true,只要有一个 list[i]大于 list[i+1]就返回false.

完善解题思路和清晰的结构

from random import randint

def sum_exist(n,p_list, i=0):
    if n<min(p_list) or i>=len(p_list): 
        return False
    else:
        for p in p_list:
            if n%p==0:
                return True
        else:
            return sum_exist(n-p_list[i],p_list,i) or sum_exist(n,p_list,i+1)
def find_s(n, p_list, sum_list, i=0):
    if n<min(p_list) or i>=len(p_list):
        return []
    else:
        for p in p_list:
            if n%p==0:
                for _ in range(n//p):
                    sum_list.append(p)
                return sum_list
        else:
            result = find_s(n-p_list[i], p_list, sum_list+[p_list[i]])
            if len(result)>0:
                return result
            else:
                return find_s(n, p_list, sum_list, i+1)
# ns = [17,7,107,43,146]
# p_lists = [[2,3,5],[3,5],[2,3,37],[3,29],[17,29,37]]

ns = []
p_lists = []
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
for i in range(10):
    num = randint(1,4)
    p_list = [PRIMES[randint(0,len(PRIMES)-1)] for _ in range(num)]
    p_list = list(set(p_list))
    p_list.sort()
    p_lists.append(p_list)
    ns.append(randint(2,100))
print("="*200)
print(f'{"n":<5}{"P_list":<20}{"Expected Result":<10}')
for n,p_list in zip(ns,p_lists):
    result = sum_exist(n, p_list)
    print(f'{str(n):<5}{str(p_list):<20}{str(result):<10}')
print("="*200)
print(f'{"n":<5}{"P_list":<20}{"Expected Result":<120}{"check":<10}{"sum_exist":<10}')
for n,p_list in zip(ns,p_lists):
    result = find_s(n, p_list, [])
    print(f'{str(n):<5}{str(p_list):<20}{str(result):<120}{str(sum(result)==n):<10}{str(sum_exist(n, p_list)):<10}')

楼上的改一下

def sum_ex(a,blist,lst=[],lst1=[]):
    if a==0:
        lst1.append(lst)
    elif a<0:
        pass
    else:
        for b in blist:
            lst_copy = lst.copy()
            lst_copy.append(b)
            cur = a-b
            sum_ex(cur,blist,lst_copy,lst1)
    if len(lst1)>0:
        return True
    else:
        return False
    
    
def find_s(a,blist,lst=[],lst1=[]):
    if a==0:
        lst1.append(lst)
    elif a<0:
        pass
    else:
        for b in blist:
            lst_copy = lst.copy()
            lst_copy.append(b)
            cur = a-b
            find_s(cur,blist,lst_copy,lst1)
    if len(lst1)>0:
        return lst1[0]
    else:
        return []

其实思路并不复杂，就是一方面向下依次尝试用 n 减去列表 b_list 中索引为 i 的元素，直到 n 小于等于索引为 i 的元素，另一方面横向递增 i，尝试使用列表中不同的元素。如果尝试的过程中找到解，则停止搜索，立即返回，不然就一直到所有元素都试过。
题目给的函数的形参，也暗示了剪枝条件：n 和 i。
纵向剪枝：n < b_list[i]，表示已经无法再继续减下去
横向剪枝：i >= len(b_list)，表示在这一层已经尝试过列表中所有元素
有解的情况必然是当前剩下的数等于列表中某个元素，也就是 n = b_list[i]，但是纵向 n 递减，横向 i 递增，所以需要两个方向的递归。
代码实现如下：

def sum_ex(n, b_list, i=0):
    if i>=len(b_list) or n < b_list[i]: return False
    if n == b_list[i]: return True
    return sum_ex(n-b_list[i], b_list) or sum_ex(n, b_list, i+1)
 
def find_s(n, b_list, sum_list, i=0):
    if i>=len(b_list) or n < b_list[i]: return []
    if n == b_list[i]: return sum_list+[b_list[i]]
    res = find_s(n-b_list[i], b_list, sum_list+[b_list[i]])
    return res if res else find_s(n, b_list, sum_list, i+1)

a = 17
b_list = [2,3,5]
print(sum_ex(a,b_list))
res = find_s(a,b_list, list())
if res:
    print(f"{'+'.join(map(str,sorted(find_s(a,b_list, list()))))}={a}")
else:
    print(res)

注意：因为是只要找到某个解就返回，所以代码的返回其实是最小的列表。
比如题目中的例子，下面两个答案都可以得到17，但是代码返回的是上面这个最小的列表。
[2,2,2,2,2,2,2,3]
[2,5,5,5]

牛顿迭代法写的递归可以嘛