通过Python3实现一些简单递归函数

大家好！今天我给大家演示一下通过Python3实现一些简单递归函数的过程。递归算法实际上就是分而治之思想的具体应用。每当你设计一个算法时，只要发现算法的处理对象变化，但是处理过程（步骤）相同，则可以优先考虑递归实现，尤其是在处理的对象个数不确定时更需要采用递归算法。设计递归算法时，只需要找到基线条件（函数返回的条件）和递归条件（继续进行递归调用的条件）即可开始编写算法实现，通常这两个条件是互斥存在的。如果您觉得这篇教程有帮助，请为我投上宝贵的一票，谢谢！

创建Pure Python项目

启动PyCharm软件，新建一个名为"AlgorithmDemo4"的Pure Python项目，然后向项目中添加一个名为""的Python文件。在文件中定义一个sum_num函数，然后调用此函数输出100以内的自然数之和。sum_num函数采用for循环实现从1到n之间的自然数累加，计算的最终结果会返回给函数调用者。测试代码编写完毕后，调试运行程序。在弹出的控制台窗口中，可以见到程序的执行结果，表示一切正常。

使用等差数列求和公式

关闭控制台窗口，返回到文件中。继续定义一个sum_num_formula函数及调用此函数计算100以内自然数的测试代码。sum_num_formula函数根据等差数列求和公式实现，具有极高的运算效率。测试代码编写完毕后，调试运行程序。在弹出的控制台窗口中，可以确定该函数的计算结果与sum_num函数相同，唯一区别是其返回值为浮点数。

递归方式计算自然数之和

关闭控制台窗口返回文件中。这次在代码中定义一个以递归方式计算N以内自然数和的函数sum_num_rec。实现该函数的实质，仍旧是累加求和，与for循环实现不同的是每次累加都是通过调用函数自身实现的，另外，递归是从n加到1，当n等于0时即停止递归（即基线条件）。sum_num_rec函数及其测试代码编写完毕后，调试运行程序，在弹出的控制台窗口中，可以见到与之前两个函数一致的输出结果，表示算法实现正确。

计算正整数阶乘

关闭控制台窗口返回到文件中，继续定义一个采用递归方式计算正整数阶乘的函数calc_factorial以及调用它计算0~10阶乘的测试代码。在实现calc_factorial函数时，需要注意0的阶乘是1，表示没有东西组合，这也是一种组合结果。因此，该函数的基线条件为n等于0，递归条件则为n大于0，对于n小于0则当做非法输入，返回None（这里应该抛异常）。

十进制数转二进制数

计算阶乘的测试代码编写完毕后，调试运行程序。在弹出的控制台窗口中，可以见到输出的0~10的阶乘计算结果。

关闭控制台窗口返回到文件中。最后，我给大家介绍一下根据短除法计算10进制数转2进制数的递归函数实现过程。短除法实际上具有非常明显的递归特性，其计算条件输入数小于2，反之则是递归条件。对于10进制转2进制而言，除了用短除法计算二进制位的值，还需要最终将每一步得到的余数颠倒，才能得到正确的结果。因此，在实现d2b函数时，将通过短除法计算二进制位的过程放到short_div函数中，颠倒结果次序的处理则放到d2b函数中。当函数编写完毕后，继续添加调用d2b函数输出0~32的二进制数的测试代码。

代码编写完毕后，调试运行程序，在弹出的控制台窗口中，可以见到按自定义格式输出的十进制数转二进制数的结果。

至此，简单递归算法就介绍完毕了。希望你在设计算法时，可以抓住分而治之思想的精髓（基线条件和递归条件），设计出高效的递归算法，Enjoy！

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。