算法图解之递归

递归就是不断调用自己，让解决方案更清晰，但是没有性能上的优势。使用情景参考Stack Overflow的一个答案：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

基线条件和递归条件

每个递归函数都有两部分：基线条件 （base case）和递归条件 （recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。”

def countdown(i):
    print(i)
    if i <= 0:  # Base case
        return
    else:  # Recursive case
        countdown(i - 1)

实例1：factorial

def max_num(list):
    if len(list) == 2:
        return list[0] if list[0] > list[1] else list[1]

    sub_max = max_num(list[1:])
    return list[0] if list[0] > sub_max else sub_max


print(max_num([1, 100, 22, 333, 31, 12]))

栈

假如你要写一系列待办事项的清单，每写一个清单就把一个便条放在桌子上，当你开始读取清单的时候，你从最上面的一张开始读，并将其删除。因此这个待办事项清单只有两种操作：压入 （插入）和弹出（删除并读取）。这种数据结构称为栈。

 

调用栈

def green(name):
    print('hello,', name)
    greet2(name)
    print('getting ready to say bye......')
    bye()


def greet2(name):
    print('how are you,', name)


def bye():
    print('ok bye')


green('Maggie')

当调用green('edward')的时候，计算机将首先为该函数调用分配一块内存。

使用这些内存的时候，变量name就被设置为edward并储存到内存中。

当调用greet2的时候，计算机也会为这个函数调用分配一块内存。

当调用greet2的时候，当前函数（greet）暂停并处于未完成状态，该函数的所有变量值还是在内存中。

执行完greet2后，回到greet函数继续执行

首先打印getting ready to say bye…，再调用 函数bye。