正在创建一个递归函数，以循环遍历生成列表的列表。。。等等

Question

首先，我使用python

我有一个名为tier1的项目列表，看起来像这样

tier1 = ['a1','a2,'a3',..,'an']

我有两个函数叫做function和functionZ

它们都以字符串作为参数，并生成如下列表输出。列表必须在执行期间生成，并且从一开始就不可用。只有第1层可用

listOutput=function（第1层[0]）

listOutput看起来像这样

listOutput = ['b1','b2,'b3',..,'bn']

下次在listOutput上使用Function时，让我们说“b1”项，它将生成

listOutput = functionA('b1')

output:
listOutput = ['bc1','bc2,'bc3',..,'bcn']

这一次，当在“bc1”上使用function时，它可能会变成空的，因此在“bc1”上使用functionZ，而将使用“bc1”，并将输出存储在某处

listOutput = functionA('bc1')

输出

listOutput = []

所以我用

listOutput = functionZ('bc1')

输出

listOutput = ['series1','series2','series3',....,'seriesn']

现在我必须返回并尝试bc2，直到bcn执行相同的逻辑。完成后，我将在“b2”上使用function。等等

每个项目的深度都是可变的

看起来像这样

只要listOutput不是空的，就必须在listOutput项或第1层项上使用function，直到它变为空为止。然后，functionZ必须用于列表中functionA为空的项目

在第1层之后，listOutput也将始终是一个列表，它还必须逐个循环，并且必须使用相同的逻辑

我正试图在此基础上创建一个递归函数，但我被卡住了

到目前为止,

def recursivefunction (idnum): #idnum will be one of the list items from tier1 or the listOutputs produced

    listOutput = functionA(idnum)

    if not listOutput:
        return functionZ(idnum)
    else:
        return recursivefunction(listOutput) 

但是我的函数返回列表，我如何让它们深入到每个列表中，直到使用functionZ，一旦使用functionZ，就转到列表中的下一项

我需要创建一种新的数据结构吗？ 我不知道从哪里开始，我应该用链表创建一些类吗

Answer 1

我对你问题的理解是：

• 有一个输入列表tier1，它是一个字符串列表
• 有两个函数，A和Z
  • A、 应用于字符串时，返回字符串列表
  • Z、 应用于字符串时，返回一些值（类型不清楚，也假定字符串列表）
• 算法：
  • 对于tier1的每个元素，将
  • 如果结果是空列表，则对元素应用Z，而不进行进一步处理
  • 否则，如果结果不是空的，则对列表应用算法

因此，在Python中：

from random import randint
# since you haven't shared what A and Z do, 
# I'm just having them do random stuff that matches your description


def function_a(s):
    # giving it a 75% chance to be empty
    if randint(1, 4) != 1:
        return []
    else:
        # otherwise between 1 and 4 random strings from some selection
        return [['a', 'b', 'c'][randint(0, 2)] for _ in range(randint(1,4))]
        # in the real case, I'm sure the result depends on `s` but it doesn't matter


def function_z(s):
    # otherwise between 0 and 4 random strings from some selection
    return [['x', 'y', 'z'][randint(0, 2)] for _ in range(randint(0,4))]


def solution(xs):
    # this is really the answer to your question:
    rs = []
    for x in xs:
        # first compute A of x
        r = function_a(x)
        # if that's the empty list
        if not r:
            # then we want Z of x instead
            r = function_z(x)
        else:
            # otherwise, it's the same algorithm applied to all of r
            r = solution(r)
        # whatever the result, append it to rs
        rs.append(r)
    return rs


tier1 = ['a1', 'a2', 'a3', 'a4']

print(solution(tier1))

请注意function_a和function_z只是生成具有指定结果类型的随机结果的函数。你没有分享A和Z的逻辑，所以很难验证结果是否符合你的要求

但是，函数solution完全按照您所说的做-如果我正确理解您对它的复杂解释的话

鉴于你的问题的解决方案基本上是这样的：

def solution(xs):
    rs = []
    for x in xs:
        r = function_a(x)
        if not r:
            r = function_z(x)
        else:
            r = solution(r)
        rs.append(r)
    return rs

甚至可以重写为：

def solution_brief(xs):
    return [function_z(r) if not r else solution(r) for r in [function_a(x) for x in xs]]

你应该重新检查你的问题描述。编程的关键是理解问题并将其分解为基本步骤。一旦您完成了这项工作，代码很快就会被理解。您选择第一种还是第二种解决方案可能取决于经验，也可能取决于微小的性能差异

顺便说一句，任何作为递归函数编写的解决方案也可以完全迭代编写——从内存和性能的角度来看，这通常更可取，但递归函数的优点是非常干净、简单，因此更易于维护

将我的编码放在我的嘴边，这里是同一问题的迭代解决方案，只是为了好玩（无论如何都不是最优的）：

def solution_iterative(xs):
    if not xs:
        return xs
    rs = xs.copy()
    stack_rs = [rs]
    stack_is = [0]
    while stack_rs:
        r = function_a(stack_rs[-1][stack_is[-1]])
        if not r:
            stack_rs[-1][stack_is[-1]] = function_z(stack_rs[-1][stack_is[-1]])
            stack_is[-1] += 1
        else:
            stack_rs[-1][stack_is[-1]] = r
            stack_rs.append(r)
            stack_is.append(0)
        while stack_is and stack_is[-1] >= len(stack_rs[-1]):
            stack_is.pop()
            stack_rs.pop()
            if stack_is:
                stack_is[-1] += 1
    return rs