python - 递归函数死于内存错误

Question

假设我们有一个翻译莫尔斯符号的函数:

• . -> -.
• - -> ...-

如果我们两次应用这个函数，我们得到例如:

. -> -. -> ...--.

给定一个输入字符串和重复次数，想知道最终字符串的长度。 (来自 Flemish Programming Contest VPW 的问题 1，取自 these slides，它提供了 Haskell 中的解决方案)。

对于给定的输入文件

4
. 4
.- 2
-- 2 
--... 50

我们期待解决方案

44
16
20
34028664377246354505728

由于我不懂 Haskell，所以这是我在 Python 中提出的递归解决方案:

def encode(msg, repetition, morse={'.': '-.', '-': '...-'}):
    if isinstance(repetition, str):
        repetition = eval(repetition)
    while repetition > 0:
        newmsg = ''.join(morse[c] for c in msg)
        return encode(newmsg, repetition-1)
    return len(msg)


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            print encode(*line.split())

它适用于前三个输入，但因最后一个输入的内存错误而死。

您将如何以更有效的方式重写它？

编辑

根据给出的评论重写:

def encode(p, s, repetition):
    while repetition > 0:
        p,s = p + 3*s, p + s
        return encode(p, s, repetition-1)
    return p + s


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            msg, repetition = line.split()
            print encode(msg.count('.'), msg.count('-'), int(repetition))

仍然欢迎对风格和进一步改进提出意见

Answer 1

考虑到您实际上不必输出结果字符串，只需输出它的长度。还要考虑 '.' 的顺序。字符串中的“-”和“-”不影响最终长度(例如“.- 3”和“-. 3”产生相同的最终长度)。

因此，我会放弃存储整个字符串，而是存储“.”的数量。和'-'的数量作为整数。