编写一个递归函数，returns 具有最长连续序列的数字

Question

如何编写一个递归函数，它接受一个 int 值和 returns 具有最长连续序列的数字？

例如，f(1122333) returns 3 和 f(1223) returns 2

我不知道如何解决这个问题，总的来说我对递归有点陌生。

Answer 1

像这样。未经测试。不过想想也很有趣。

伪代码：

（假设整数除法）

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);

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

一个注意事项：在平局的情况下，匹配号码的第一个子串（实际上是原始号码中的最后一个子串）将被 returned。如果需要其他行为，则将两个 > 与 >= 互换。

Answer 2

我能想到的最简单的事情就是通过 tail recursion 来做到这一点。在该函数中，我将有一个用于递归的私有函数。首先，我会将整数转换为一个列表，其中每个数字都作为一个单独的元素分隔。这个递归私有函数接受一个元素列表、我们正在调查的数字、拥有最长连续序列的当前数字和一个描述我们已经看到了多少次的计数。计数很重要，因为我们将计算遇到特定参考号的次数。该列表作为输入很重要，因为我们可以通过跳过该列表的第一个元素来简单地为每次调用提供一个少了一个元素的列表。最终，我们将只得到列表中的一个数字，即 基本情况。

换句话说，对于任何递归算法，您都需要 base 情况，这是我们将停止和 return 的地方，以及递归我们需要调用修改输入的函数的情况。

基本情况是我们提供一个数字的数字。这意味着我们已经到达了数字的末尾。如果是这种情况，我们需要做的就是检查这个值是否等于当前认为是连续的当前值。如果此值匹配，我们将当前连续计数加 1。如果此值超过当前最长连续计数，我们将 return 此单个数字作为属于该数字的数字最长的连续序列。如果不是，那么在我们决定进行此检查之前，我们只需 return 这个值是多少。

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

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

废话不多说，这就是我写的。该函数称为 longest_consecutive_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

请注意，如果有多个数字共享相同数量的连续数字，则只有产生该长度连续数字的第一个数字才是输出。正如 Ron Thompson 在他的 post 中指出的那样，如果您希望 最近的 或满足要求的最后一个连续数字，则使用 >= 而不是 > 检查计数时。

编写一个递归函数，returns 具有最长连续序列的数字

Writing a recursive function that returns the digit with longest consecutive sequence

python

recursion

digits

python-2.7