递归基础表示

Question

我很高兴在 Python 中再次学习递归，虽然基础知识很容易掌握，但似乎有一点我只是失去了递归解决问题的能力。

例如下面的问题。

写一个递归函数 base 有两个参数，n，一个以 10 为底的正整数，和 b，一个介于 2 和 9 之间的整数。函数 returns 以 b 为底的表示数字 n。数字的基数 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

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

在这种情况下，我们首先要获取个位的数字，这很简单：只需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'

或者您可以直接将递归函数定义为 return 一个字符串

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

Answer 2

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

你必须知道什么时候停止！
您必须能够根据同一问题的较小版本的解决方案来表达问题。

让我们看看你的 "problem":

You want to produce a string that represents n written in base b.

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

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

进行递归时，更有效的形式是使用 tail recursion，它在每个步骤中都进行一些计算并携带一个累加器，在最后一步中您在累加器中得到答案，因此你不需要在递归调用返回的路上做额外的工作，如果你能这样做，很容易把它变成一个循环，反之亦然，这就是你在 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'

递归基础表示

Recursive base representation

python

python-3.x

recursion

base

产出