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

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

我的目标是编写一个反转整数数字的递归程序.

由于这是业内人士不希望达到的目标,因此这对于一个班级来说是好的.特别是,没有明智的人会通过递归来解决这个问题,即使他们有这个问题.因此,教授递归是一个糟糕的问题,因为非递归解决方案非常简单.

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

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

(这就提出了一个有趣的问题,即如何处理适合int但却没有反转的数字,比如1000000009.让我们暂时忽略这些问题.)

让我们从基础开始吧.每个递归方法都具有相同的结构:

• 我们是否在基础案例中？如果是,请返回结果.
• 我们不是基本情况.
• 将问题分解为更小的问题
• 以递归方式解决每个问题
• 结合解决方案来解决更大的问题
• 返回结果.

让我们天真地将这种模式应用到您的问题中,看看会发生什么.

基本案例很简单:

• 从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.然后ReverseHelper回来0,好.零工作.

假设number是3.然后我们调用ReverseHelper(3, 0)哪些调用ReverseHelper(0, 3)返回3.一位数的数字工作.

假设number是35.我们调用ReverseHelper(35, 0)哪个调用ReverseHelper(3, 5)哪个调用ReverseHelper(0, 53)返回53.两位数字起作用.

等等.

练习:有一种直接的方法来处理反转int的问题,其中反转不适合int; 它是什么？

你看,我希望为什么使用累加器来调用这种技术.随着递归的进行,期望的结果逐渐累积,然后在递归到达其基本情况时返回.

现在,请注意这种技术与原始程序的关系.您正在使用静态字段作为累加器.永远不要那样做!永远!递归方法不应该依赖于它们对外部状态的正确性. 相反,将递归消耗的值传递给对辅助方法的递归调用.

仔细研究这项技术.这是编写递归程序的强大技术.在函数式语言中,这样的操作被称为fold或reduce; 期待那些进一步的灵感.在C#中,它被调用Aggregate并用于生成序列的汇总结果.

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

• 我们是否在基础案例中？如果是,则从累加器返回结果.
• 我们不是基本情况.
• 将问题分解为更小的问题
• 通过在递归调用上将有关解决方案的信息累积到累加器中来递归地解决每个问题.
• 结合解决方案来解决更大的问题
• 返回结果.

为什么这种技术如此有价值？在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理论中的关键工具.