编写递归函数，返回具有最长连续序列的数字

Question

如何编写一个接受int值并返回具有最长连续序列的数字的递归函数？

例如，f（1122333）返回3，而f（1223）返回2

我不知道如何处理这个问题，而且我对递归一般来说是个新手。

Answer 1

我能想到的最简单的事情就是通过尾部递归来实现这一点。在函数中，我将有一个用于递归的私有函数。首先，我将把整数转换成一个列表，其中每个数字作为一个单独的元素分开。这个递归私有函数包含元素列表、我们正在研究的数字、保存最长连续序列的当前数字以及描述我们看到多少次的计数。计数很重要，因为我们将计算遇到特定参考号的次数。列表是一个重要的输入，因为我们可以跳过列表的第一个元素，为每个调用提供一个少一个元素的列表。最后，我们将只讨论列表中的一个数字，这是基本情况。

换句话说，对于任何递归算法，您都需要基本情况，即我们将停止并返回某些内容，以及我们需要在修改输入的情况下调用函数的递归情况。

基本情况是当我们提供一个数字时。这意味着我们已经到达了数字的末尾。如果是这种情况，我们需要做的是检查该值是否等于当前认为连续的当前值。如果该值匹配，则将当前连续计数增加1。如果此值超过当前最长连续计数，我们将返回此单个数字作为与最长连续序列相关的数字。如果没有，那么我们只需在决定执行此检查之前返回此值。

递归情况稍微复杂一些。给定我们正在查看的数字，我们检查该数字是否等于被视为连续流一部分的数字。如果是，则将此数字的计数增加1，然后检查此计数是否大于当前最大的连续计数。如果是，那么我们需要将当前最长值更新为此值，并更新最长计数。如果不匹配，我们将计数重置回1，因为这是遇到的第一个此类数字。要匹配的当前值将是该值，我们将在提交从第二个索引开始的值列表时递归，并更新其他变量。

当我们从第二个索引开始不断递归和指定列表的值时，我们将有效地从开始到最后到达列表的最后一个元素时在列表中进行线性搜索，这就是我们停止的地方。

不用再多说了，这就是我写的。该函数被称为“最长连续值”（longest\u continuous\u value），它接受一个整数：

# Function that determines the value that has the longest consecutive sequence
def longest_consecutive_value(value):

    # Recursive function
    def longest_recursive(list_val, current_val, current_longest_val, longest_count, count):
        # Base case
        if len(list_val) == 1:

            # If single digit is equal to the current value in question,
            # increment count
            if list_val[0] == current_val:
                 count += 1

            # If current count is longer than the longest count, return
            # the single digit
            if count > longest_count:
                return list_val[0]
            # Else, return the current longest value
            else:
                return current_longest_val
        # Recursive case
        else:
            # If the left most digit is equal to the current value in question...
            if list_val[0] == current_val:
                # Increment count
                count += 1
                # If count is larger than longest count...
                if count > longest_count:
                    # Update current longest value
                    current_longest_val = list_val[0]
                    # Update longest count
                    longest_count = count
            # If not equal, reset counter to 1
            else:
                count = 1
                # Current value is the left most digit
                current_val = list_val[0]

            # Recurse on the modified parameters
            return longest_recursive(list_val[1:], current_val, current_longest_val, longest_count, count)

    # Set up - Convert the integer into a list of numbers
    list_num = map(int, str(value))

    # Call private recursive function with initial values
    return longest_recursive(list_num, list_num[0], list_num[0], 0, 0)

以下是一些示例案例（使用IPython）：

In [4]: longest_consecutive_value(1122333)
Out[4]: 3

In [5]: longest_consecutive_value(11223)
Out[5]: 1

In [6]: longest_consecutive_value(11223334444555555)
Out[6]: 5

In [7]: longest_consecutive_value(11111111122)
Out[7]: 1

In [8]: longest_consecutive_value(1122334444)
Out[8]: 4

请注意，如果有多个数字共享相同数量的连续数字，则仅输出产生该长度连续数字的第一个数字。正如罗恩·汤普森（RonThompson）在他的帖子中指出的那样，如果您希望得到满足要求的最新或最后一个连续数字，那么请使用<代码>

Answer 2

像这样的。未测试。不过想起来很有趣。

伪代码：

（假设整数除法）

Def number helperLongest(number myNum): 
    Return longest(myNum, -1, 0, -1, 0)

Def number longest(number myNum,number prevLongest, number numOfPrevLong, number currentLongest,number numOfLongest):
    If (myNum/10 < 1) //base case
        If (myNum == currentLongest)
            numOfLongest++
        Else //deal with corner case of < 10 input
            If (numOfLongest > numOfPrevLong)
                prevLongest = currentLongest
                numOfPrevLongest = numOfLongest
            currentLongest = myNum
            numOfLongest = 1
        return (numOfLongest>numOfPrevLong)?currentLongest:prevLongest
    Else //recurse
        if(myNum%10 == currentLongest) 
            numOfLongest++;
        Else //have to break the chain 
             if (numOfLongest > numOfPrevLongest)
                 prevLongest = currentLongest
                 numOfPrevLongest = numOfLongest
             currentLongest = myNum%10
             numOfLongest = 1
        myNewNum = myNum/10;
        return longest(myNewNum,prevLongest,numOfPrevLong,currentLongest,numberOfLongest);

换言之：从末尾开始，逐位遍历数字。如果当前最后一个数字与它前面的数字匹配，则递增计数器。如果没有，并且它比以前的最大值大，请保存它。将当前数字重置为当前最后一个数字，并重置计数器。切掉最后一个数字。将较小的数字和所有这些信息反馈到函数中，直到您得到最后一个数字（原始数字的第一个数字）。将当前计数器与存储的最大值进行比较，然后返回较大值。

注意：如果是平局，将返回匹配号码的第一个子串（实际上是原始号码中的最后一个子串）。如果需要其他行为，则交换这两种行为