在python中如何用用递归

Question

在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.

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

Answer 1

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}')