递归函数死于内存错误

Question

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

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

如果我们两次应用此函数,我们得到例如:

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

给定输入字符串和重复次数,想知道最终字符串的长度.(佛兰芒编程竞赛 VPW中的问题1 ,取自这些在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"产生相同的最终长度).

因此,我会放弃存储整个字符串而是存储'.'的数量.和' - '的数量为整数.