概念
一个函数调用自身称为递归调用
一个会调用自身的函数称为递归函数
说明
凡是循环能干的事,递归都能干
以后尽量少使用递归,递归不好写,效率低
写递归的过程
a、写出临界条件
b、找这一次和上一次的关系
c、假设当前函数已经能用,调用自身计算上一次结果,在求出本次结果
示例
需求:编写函数,实现给函数一个大于等于1的整数数字,求1+2+……+n的和
# 普通实现
def my_sum1(n):
sum = 0
for i in range(1, n + 1):
sum += i
return sum
<span class="hljs-comment"># 递归实现</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">my_sum2</span><span class="hljs-params">(n)</span>:</span>
<span class="hljs-keyword">if</span> n == <span class="hljs-number">1</span>:
<span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
<span class="hljs-keyword">else</span>:
<span class="hljs-keyword">return</span> my_sum2(n - <span class="hljs-number">1</span>) + n
栈和队列:两种数据存储格式
代码
myStack = []
# 压栈(往栈结构中存储数据)
myStack.append(1)
print(myStack)
myStack.append(2)
print(myStack)
myStack.append(3)
print(myStack)
# 出栈(从栈结构中提取数据)
myStack.pop()
print(myStack)
myStack.pop()
print(myStack)
myStack.pop()
print(myStack)
深度优先算法
代码
from collections import deque
q = deque([1,2,3,4])
# 进队
q.append(5)
print(q)
q.append(6)
print(q)
# 出队
q.popleft()
print(q)
q.popleft()
print(q)
q.popleft()
print(q)
q.popleft()
print(q)
广度优先算法
栈区:由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈 堆区:一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表 全局区(静态区):全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域,程序结束后由系统释放 文字常量区:常量字符串就是放在这里的,程序结束后由系统释放 程序代码区:存放函数体的二进制代码
stack:相对较高 heap:相对较低