递归

基线条件指的是函数不再调用自己, 相当于一个出口; 递归条件指的是函数自己调用自己

栈

栈又称为栈或堆叠, 是计算机科学中一种特殊的串列形式的抽象数据类型, 其特殊之处在于只能允许在链表或数组的一端 (称为堆栈顶端指针) 进行加入数据 (push) 和输出数据 (pop)的运算 (也就是压入和弹出)。 另外栈也可以用一堆数组或链表的形式来完成。 堆栈的另外一个相对的操作方式称为队列。由于堆栈数据结构只允许在一端进行操作, 因此按照后进先出的原理运作

实例

# coding: utf-8
# 阶乘

def  fact(num):
    if num == 1:
        return num
    return num * fact(num - 1)

print(fact(5)) # 120

# coding: utf-8
"""
递归求列表的和
基本思路:
基线条件, 如果列表只有一个元素, 那么就返回这个元素
线性条件, 计算列表除第一个元素外其他数字的和, 将其再与第一个元素相加, 然后再返回
"""

def sum_arr(arr):
    if len(arr) == 1:
        return sum(arr)
    else:
        return arr[0] + sum_arr(arr[1:])

arr = [i for i in range(100)]
print(sum_arr(arr))

# coding: utf-8
"""
递归求列表包含的元素数, 跟上面那题没上面区别- -
基线条件, 如果是空列表, 则返回 0
线性条件, 计算列表除第一个元素外的其他元素的个数和, 然后再加上 1 返回
"""

def count(arr):
    if arr == []:
        return 0
    return 1 + count(arr[1:])

arr = [i for i in range(5)]
print(count(arr))

小结

• 递归条件指的是函数自己调用自己;
• 每个递归函数都有两个条件: 基线条件和递归条件;
• 栈有两种操作: 压入和弹出;
• 所有函数调用都进入调用栈;
• 调用栈可能很长, 这将占用大量的内存.