时间戳

首页 > 解决方案 > 如何使用递归生成交替子串

python - 如何使用递归生成交替子串

问题描述

我有一个练习题，要求我使用递归和迭代生成 x 个交替子字符串，即“#-”和“#--”。eg.string_iteration(3) 生成“#-#--#-”。

我已经成功地实现了迭代方法的解决方案，但是我在开始使用递归方法时遇到了麻烦。我该如何进行？

迭代法

def string_iteration(x):
    odd_block = '#-'
    even_block = '#--'
    current_block = ''
    if x == 0:
        return ''
    else:
        for i in range(1,x+1):
            if i % 2 != 0:
                current_block += odd_block
            elif i % 2 == 0:
                current_block += even_block
            i += 1
        return current_block

标签： pythonrecursion

解决方案

对于递归解决方案，您需要一个基本情况并使用其他值再次调用该函数，以便最终获得所需的输出。在这里，我们可以像 - 一样递归解决这个问题string_recursive(x) = string_recursive(x-1) + string_recursive(x-2) + ... + string_recursive(1)。

def string_recursion(x, parity):
    final_str = ''
    if x == 0:
        return ''
    if parity == -1: # when parity -1 we will add odd block
        final_str += odd_block
    elif parity == 1:
        final_str += even_block
    parity *= -1    # flip the parity every time
    final_str += string_recursion(x-1, parity)
    return final_str

odd_block = '#-'
even_block = '#--' 
print(string_recursion(3, -1)) # for x=1 case we have odd parity, hence -1
# Output: #-#--#-

推荐阅读