递归基表示形式

Question

我很高兴在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]

如果有人愿意引导我递归地解决这个问题，我们将不胜感激。

另外，学习递归思考以练习一个又一个问题的最佳方法吗？我习惯于让新概念立即为我点击，我用递归撞到这堵砖墙的事实对我来说有点令人担忧。

Answer 1

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

1. 你必须知道什么时候停止！

2. 您必须能够用同一问题的较小版本的解决方案来表达问题。

让我们看看你的"问题"：

您希望生成一个字符串，该字符串表示以基本b编写的n。

一些快速的经验法则：如果问题涉及"整数"，则可能的停止点为零。如果它涉及"字符串"，则可能的停止点是空字符串。如果它涉及复杂的数据结构（如列表），则可能的停止点是空数据结构。（这并不总是正确的。但课堂作业总是如此。;-)

无论如何，您已经想到了使用 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)

Answer 2

我主要修改了您的（已经很漂亮的）解决方案。 递归的想法是将解决方案分解为更小的子问题。

在这种情况下，我们首先要获取 one 位置的数字，这很容易：只需 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)

Answer 3

在进行递归时，更有效的形式是使用尾递归，它在每一步中都进行一些计算并携带一个累加器，在最后一步中你在累加器中有答案，因此你不需要额外的工作从递归调用回来，如果你能做到这一点，很容易将其更改为循环，反之亦然， 这就是你在Haskell中必须做的事情，例如，如果你需要一个类似循环的计算，你可以以尾递归的形式进行。

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

BASE='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' #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字符串中是不可变的，因此任何更改它们的操作都会复制它，因此为了避免我，我使用列表）

测试

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