递归不会做它应该做的事情

本文关键字：递归 | 更新日期: 2023-09-27 17:56:04

我有一个函数，它接受一个整数值并返回 [i/2， i/3， i/4] 的列表，其中 i ！= 0。我还有一个递归，它应该将函数 （i） 计算到由于达到 0 而无法计算的程度。然后，我计算列表中有多少个零并输出它。

C#：

    static void Main(string[] args)
    {
        int input = int.Parse(Console.ReadLine());
        int zeroes = 0;
        List<int> myList = ATM(input);
        foreach(var number in myList.ToArray())
        {
            if (number != 0)
            {
                myList.AddRange(ATM(number));
            }
            else
            {
                continue;
            }
        }
        foreach (var zero in myList)
        {
            if (zero == 0)
            {
                zeroes += 1;
            }
        }
        Console.WriteLine(zeroes);
        Console.ReadKey();

        Console.ReadKey();
    }
    static List<int> ATM(int value)
    {
        List<int> exchangeCoins = new List<int>();
        if (value != 0)
        {
            exchangeCoins.Add(value / 2);
            exchangeCoins.Add(value / 3);
            exchangeCoins.Add(value / 4);
        }
       else
        {
            throw new Exception("Value can't be zero!");
        }
        return exchangeCoins;
    }
}

7 应该返回 15 个 0，但它返回 6 个零。为什么？

递归不会做它应该做的事情

让我们逐步完成您的代码

static void Main(string[] args)
    {
        int input = 7;
        int zeroes = 0;
        List<int> myList = ATM(input);

我的列表 => [3,2,1] 

        foreach(var number in myList.ToArray())
        {
            if (number != 0)
            {
                myList.AddRange(ATM(number));
            }
            else
            {
                continue;
            }
  • 3 mylist => [3,2,1,1,1,0]
  • 在 2 mylist 之后 => [3,2,1,1,1,0,1,0,0]
  • 在 1 个 mylist 之后 => [3,2,1,1,1,0,1,0,0,0,0,0] 
        }

手动数零...你看到 6 个零

        foreach (var zero in myList)
        {
            if (zero == 0)
            {
                zeroes += 1;
            }
        }
        Console.WriteLine(zeroes);
        Console.ReadKey();

        Console.ReadKey();
    }
    static List<int> ATM(int value)
    {
        List<int> exchangeCoins = new List<int>();
        if (value != 0)
        {                                 // 7 3 2 1
            exchangeCoins.Add(value / 2); // 3 1 1 0
            exchangeCoins.Add(value / 3); // 2 1 0 0
            exchangeCoins.Add(value / 4); // 1 0 0 0
        }
       else
        {
            throw new Exception("Value can't be zero!");
        }
        return exchangeCoins;
    }
}

这就是为什么你的代码返回 6

如果你的目标是得到15个零，那么你必须设计递归的ATM：

static void Main( string[ ] args )
{
    int input = int.Parse( Console.ReadLine() );
    int zeroes = 0;
    List<int> myList = ATM( input );
    foreach ( var zero in myList )
    {
        if ( zero == 0 )
        {
            zeroes += 1;
        }
    }
    Console.WriteLine( zeroes );
    Console.ReadKey();

    Console.ReadKey();
}

ATM 中的递归调用

static List<int> ATM( int value )
{
    List<int> exchangeCoins = new List<int>();
    if ( value != 0 )
    {
        exchangeCoins.Add( value / 2 );
        exchangeCoins.Add( value / 3 );
        exchangeCoins.Add( value / 4 );
        // recursive call on the three items
        foreach ( var item in exchangeCoins.ToArray() )
        {
            exchangeCoins.AddRange( ATM( item ) );
        }
    }
    return exchangeCoins;
}

你怎么知道 7 应该返回 15 个 0？

第一次迭代，您将有 3 个条目

x1、x2 和 x3

之后，对于每个条目（3个条目），您最多将有3个条目

x1

生成 x11、x12 和x13
x2 生成 x21、x22 和x23
x3 生成 x31、x32 和x33

所以还有 9 个条目。总计：9 + 3 = 12

如果你最多有 15 个数字，你怎么能有 12 个 0？？

相关文章：