反转整数数字数字的递归函数

Question

我的目标是编写一个递归程序来反转整数的数字。当我测试第一个元素时，代码有效。但是，它不适用于其他两种情况，例如对于 reverse(456) 它打印 321654，对于 reverse(731) 它打印 321654137。我认为问题出在 public static variable reverted 上。

有人可以帮助我理解问题并解决它吗？

using System;  
public class Program
{
    public static void Main(string[] args)
    {
        reverse(123);
        reverse(456);
        reverse(731);
    }

    public static int reverted=0;

    public static void reverse(int number)
    {
        if (number!=0)
        {
            int remainder = number % 10;
            reverted = (reverted*10)+remainder;
            reverse(number/10);
        } 
        else
            Console.WriteLine(reverted);
    }
}

Answer 1

试试我的方法：

public static int reverse(int number, int result = 0, int reminder = 0)
{
    if (number == 0)
    {
        return result * 10 + reminder;
    }
    return reverse(number / 10, result * 10 + reminder, number % 10);
}

调用方法reverse(123)即可。其他两个参数 result 和 reminder 是可选的，因为它们有默认值。

Demo here

编辑：

这是上面代码的简明版本：

public static int reverse(int number, int result = 0)
{
    if (number == 0)
    {
        return result;
    }
    return reverse(number / 10, result * 10 + number % 10);
}

或者配合使用三元运算符：

public static int reverse(int number, int result = 0)
{
    return number == 0 ? result : reverse(number / 10, result * 10 + number % 10);
}

Answer 2

My goal is to write a recursive program that reverse the digits of an integer number.

由于这是业内没有人希望达到的目标，因此 class 的可能性很大。特别是，没有一个明智的人会用递归来解决这个问题，即使他们有这个问题。所以这是一个教递归的糟糕问题，因为非递归解决方案非常简单。

您不太了解递归的可能性也很大。从某种意义上说，这是一个很好的练习，因为它要求您使用一种称为 累加器 的特殊技术来实现递归解决方案。

此外，即使您修复了错误，您的解决方案也不会产生所需的数量。它打印它，那是完全不同的。我们希望能够产生结果，而不仅仅是显示它。

（这就提出了一个有趣的问题，即如何处理适合 int 但其反转不适合的数字，例如 1000000009。让我们暂时忽略这些问题。 )

所以让我们从基础开始。每个递归方法都具有相同的结构：

我们处于基本情况吗？如果是，return结果。
我们不在基本情况下。
将问题分解成更小的问题
递归地解决每个问题
结合解决方案来解决更大的问题
Return结果。

让我们天真地将此模式应用于您的问题，看看会发生什么。

基本情况很简单：

从 0 到 9 的任何非负数的倒数都是它本身。

递归的情况是什么？假设我们有 157

将数字除以 10 得到更小的数字 15
反转较小的数字 -- 51
将原始数字的低位数字附加为反转后的较小数字的高位数字，751 ---等等，我们如何做到这一点？

不清楚如何执行最后一个操作。

我们需要更聪明。

这就是你要做的。（我省略了拒绝负数的错误检查。）

static int ReverseHelper(int number, int accumulator) =>
  number == 0 ? 
    accumulator : 
    ReverseHelper(number / 10, accumulator * 10 + number % 10);

public static int Reverse(int number) =>
  ReverseHelper(number, 0);

让我们来看一些案例。

假设 number 是 0。然后ReverseHelperreturns0，好。零作品。

假设 number 是 3。然后我们调用 ReverseHelper(3, 0) 调用 ReverseHelper(0, 3)，return 调用 3。一位数有效。

假设 number 是 35。我们调用ReverseHelper(35, 0)，调用ReverseHelper(3, 5)，调用ReverseHelper(0, 53)，调用returns 53。两位数有效。

以此类推

练习： 有一种直接的方法可以处理反转 int 不适合 int 的问题；这是什么？

你明白我希望为什么使用 累加器 调用此技术。期望的结果是随着递归的进行逐渐累积，然后当递归到达其基本情况时return。

现在，请注意此技术与您的原始程序的关系。 您正在使用静态字段作为累加器。永远不要那样做！曾经！递归方法的正确性不应依赖于外部状态。 相反，将您将递归使用的值传递到辅助方法的递归调用中。

仔细研究这个技巧。这是编写递归程序的强大技术。在函数式语言中，这样的操作称为 fold 或 reduce；从中寻找更多灵感。在 C# 中，它称为 Aggregate，用于生成序列的汇总结果。

使用累加器的递归模式是：

我们处于基本情况吗？如果是，return 累加器的结果。
我们不在基本情况下。
将问题分解成更小的问题
递归地解决每个问题，通过在递归调用时将有关解决方案的信息累积到累加器中。
结合解决方案来解决更大的问题
Return结果。

为什么这项技术如此有价值？在 C# 中，这不太重要，但在 尾递归函数式语言 中，编译器通常可以将使用累加器的递归方法优化为比非尾递归方法更高效的代码，所以这是另外一回事研究。

它在 C# 中很有价值，因为 使用累加器的尾递归方法可以通过简单的程序转换过程轻松转换为非递归方法。

让我们看看如何。我们有：

static int ReverseHelper(int number, int accumulator) =>
  number == 0 ? 
    accumulator : 
    ReverseHelper(number / 10, accumulator * 10 + number % 10);

让我们将其重写为语句：

static int ReverseHelper(int number, int accumulator)
{
  if (number == 0)
    return accumulator;
  else
    return ReverseHelper(number / 10, accumulator * 10 + number % 10);
  }
}

现在让我们为所有子表达式制作解释变量：

static int ReverseHelper(int number, int accumulator)
{
  if (number == 0)
    return accumulator;
  else 
  {
    int newNumber = number / 10;
    int newAccumulator = accumulator * 10 + number % 10;
    return ReverseHelper(newNumber, newAccumulator);
  }
}

到目前为止一切顺利。但是现在我们注意到我们可以把整个事情变成一个循环！

static int ReverseHelper(int number, int accumulator)
{
  while (true) 
  {
    if (number == 0)
      return accumulator;
    else 
    {
      int newNumber = number / 10;
      int newAccumulator = accumulator * 10 + number % 10;
      number = newNumber;
      accumulator = newAccumulator;
      // And now the loop starts over!
    }
  }
}

当然，我们看到这现在具有问题的直接非递归解决方案的形式。

这应该能让您深入了解递归程序的本质：

每个递归程序都可以转化为尾递归程序，尽管并不总是很容易看出如何。
每个尾递归程序都可以转化为非递归循环。
反之亦然！每个有循环的程序都可以转化为尾递归程序！

同样，仔细研究这些简单的技巧。了解递归和非递归程序之间的关系是 CS 理论的关键工具。

Answer 3

使用递归反转输入数字

    public static int ReverseRecursive(int number)
    {
        int remainder = number % 10;
        number = number / 10;
        if (number < 1)
            return remainder;
        return ReverseRecursive(number) + remainder * Convert.ToInt32(Math.Pow(10, number.ToString().Length));
    }

反转整数数字数字的递归函数

Recursive function to reverse the digit of an integer number

c#

recursion

digit

使用递归反转输入数字