[Python3算法(4)] 简单递归算法[TZZ]

1、启动PyCharm软件，新建一个名为“AlgorithmDemo4”的“Pure Python项目”，然后向项目中添加一个名为“main.py”的Python文件（具体步骤请参考引用教程）；

2、在main.py文件中定义一个sum_num函数，然后调用此函数输出100以内的自然数之和。sum_num函数采用for循环实现从1到n之间的自然数累加，计算的最终结果会返回给函数调用者。测试代码编写完毕后，调试运行程序。在弹出的控制台窗口中，可以见到程序的执行结果，表示一切正常；

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

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

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

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

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

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

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