03_recursion

第3章 递归

• 递归只是让解决方案更清晰，并没有性能上的优势。
• 在有些情况下，使用循环的性能更好。

• 如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

1. 基线条件和递归条件

   • 每个递归函数都有两个部分：基线条件（base case）和递归条件（recursive case）。

   • 基线条件解决的是最基础的问题，也是递归的出口。没有基线条件，将形成无限循环。

   def fact():
       if x == 1:      # 基线条件
           return 1
       else:           # 递归条件
           return x * fact(x-1)

2. 栈

   • 调用另一个函数时，当前函数暂停并处于未完成状态，当前函数的信息存储在栈中。
   • 所有函数调用都进入调用栈。
   • 调用栈可能很长，这将占用大量的内存。