我很高兴再次学习Python中的递归，而基础很简单，似乎有一点我只是失去了递归解决问题的能力。递归基表示法

例如下面的问题。

写递归函数基础，有两个参数，N，基座10的正整数，b，2和9之间的整数。函数返回数量n的基极b表示。数字的基数b表示使用数字0，..，b-1，数字的位置表示基数的功率。

>>> base(5,3) # write 5 in base 3 
'12' 

>>> base(887,7) # write 887 in base 7 
'2405'

我没有使用递归完成问题。

def base(n, b): 
    if n == 0: 
     return [0] 
    digits = [] 
    while n: 
     digits.append(int(n % b)) 
     n //= b 
    return digits[::-1]

如果有人愿意通过递归解决这个问题，我将不胜感激。

此外，学习思考问题后递归思考问题的最佳方法是什么？我习惯于让新的概念立即点击我，这个事实让我感到有些担忧，这个事实是我用这种递归方法打砖墙。

来源

2016-02-27 23k

“而这并返回正确的答案，它是低效做” - 是什么让你觉得你的迭代求解效率低下？似乎没有任何明显的缺陷。严格地说，有些算法具有更好的渐近运行时间，但是它们需要更复杂的背景知识，而不是您可以合理预期拥有的方法，并且只有涉及数百位数字时，它们才会变得有价值。 – user2357112

另外，请记住递归函数通常由于其大的开销而导致性能不佳 – RafaelC

等待Python 3？你应该用'// ='代替'/ ='进行地板划分。也许这就是为什么你认为它效率低下的原因;如果你使用真正的分区，你会得到错误的结果。 – user2357112

有一个递归程序两个基本部分组成：

您必须知道什么时候停止！
您必须能够通过解决方案来解决相同问题的较小版本。

让我们来看看你的“问题”：

你要产生代表n写在基地b的字符串。

一些快速经验法则：如果问题涉及“整数”，则可能的停止点为零。如果涉及“字符串”，则可能的停止点是空字符串。如果它涉及像列表这样的复杂数据结构，则可能的停止点是空的数据结构。（这并非总是如此，但对课堂作业来说总是如此;;）

无论如何，你已经使用n作为你最重要的变量，并测试它为零的想法。

我打算建议那是错的。（因为...）

让我们尝试一个略有不同的终止条件：n < b。在这种情况下，你知道你可以产生一个数字。

所以：

if n < b: 
    return str(n)

做完这些，我们能做些什么？那么，你的代码的其余部分是在几乎现货：做递归时

def base(n, b): 
    if n < b: return str(n) 
    return base(n // b, b) + str(n % b)

来源

2016-02-27 01:47:37

非常有帮助，我之前没有注意到终止条件的问题。我会问你和我以前对我的问题的回答一样的问题。你如何决定何时迭代地递归解决问题？看起来递归解决问题的时间要短得多，并且直截了当，但从我的理解来看，并不总是最有效的方法。 – 23k

大多数语言的递归受堆栈深度的限制。如果你有一种优化“尾递归”的语言，你可以做你喜欢的事情。但是大多数语言都不会，所以如果我能“看到最后”，我倾向于避免递归。例如，像这样的问题有一个明显的转换到循环。但是遍历树之类的东西没有这么明显的转换（没有实现我自己的堆栈等）。所以我会在终止条件不明显的时候递归，并且当我看到如何终止时循环。 –

我大多修改了你的（已经非常好的）解决方案。递归的想法是将解决方案分解成更小的子问题。

在这种情况下，我们首先要获取那个位置的数字，这很容易：只需n%b。之后，我们需要弄清楚如何将数字的其余部分转换为基数b。这是我们递归的部分，直到数字的其余部分为0，此时我们完成了。

def base_recur(n,b): 
     if n == 0: 
      return [] 
     return base_recur(n//b, b) + [n%b]

输出

base_recur(887,7) 
    [2, 4, 0, 5] 

    base(5,3) 
    [1, 2]

如果你想有一个字符串表示，你可以用与结果join

"".join(str(dig) for dig in base_recur(887,7)) 
'2405'

或者，你可以定义递归函数本身返回一个字符串

def base_recur(n,b): 
     if n == 0: 
      return '' 
     return base_recur(n//b, b) + str(n%b)

来源

2016-02-27 01:28:27

在没有'TypeError'的情况下获得函数内部字符串表示的最佳方式是什么？ – 23k

，更有效的方式是通过使用tail recursion是做计算的位在每一个步骤和携带蓄电池，并在最后一步你在累加器中有答案，因此在递归调用的时候你不需要额外的工作，并且如果你可以这样做，很容易将它变成循环，反之亦然，那就是你例如，在Haskell中，如果你需要一个类似循环的计算，你可以用尾递归的方式来完成它。

现在这个问题可以得到解决这样

BASE='ABCDEFGHIJKLMNOPQRSTUVWXYZ' #until base 36, because why not :) 

def base(n,b,acc=None): 
    if acc is None: # I need a accumulator, if I don't get one I provide one 
     acc=[] 
    if n < b: 
     acc.append(BASE[n]) 
     return "".join(reversed(acc)) 
    else: 
     n,d = divmod(n,b)  # n//b and n%b at once 
     acc.append(BASE[d]) 
     return base(n,b,acc)

（我用一个列表作为蓄能器，因为在Python字符串是inmutables，使改变他们的任何操作做一个副本，所以饶了我的我用一个列表）

测试

>>> base(0,16) 
'0' 
>>> base(42,16) 
'2A' 
>>> base(5,3) 
'12' 
>>> base(420,25) 
'GK' 
>>> base(25,25) 
'10' 
>>> base(42,2) 
'101010'

来源

2016-02-27 02:50:38 Copperfield

递归基表示法

回答

输出

相关问题