递归函数

# 1. 什么是递归函数
#
# 首先我们来回忆一下函数的嵌套
#
# 函数的嵌套分两种模式：嵌套定义与嵌套调用
#
# 函数的嵌套定义在闭包函数处应用的特别开心
#
# 那么现在，在递归函数中，我们就用到了函数的嵌套调用
#
# 递归函数就是函数的嵌套调用的一种特殊情况
#
# 定义函数时在函数体内调用自身就叫做递归函数
#
# 这是百度百科定义的递归：程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
#
# 函数的递归必须满足两个原则：
#
# （1） 每进入下一层递归循环，问题规模需要有所减小
#
# （2） 必须有明确的结束条件或者必须有明确的进入下一层递归的条件
#
# 我们每进入下一层递归循环，相应的问题规模应该有所减小，不然我们会陷入一个死循环中，问题只要不解决，就会无休止的进入下一层递归循环。每调用一个函数，就会在内存中申请一个空间，等函数结束才会清除这块内存空间，那么我们无休止的调用函数，就会使得内存被占满，我们的电脑就会被卡死。
#
# 我们需要有一个明确的结束条件，当条件成立，开始一层一层的往前递推。或者说我们需要有一个明确的进入下一层递归的条件，条件成立时我们才进入下一层递归。
#
# 递归有两个明确的阶段：
#
# （1）回溯：一层一层的递归调用 #注意：回溯完成后，不代表函数体的结束，多用return结束，
#
# （2）递推：在某一层结束递归，然后一层层的返回 #返回的值打印出来就是进入回溯过程中的内容
#
# 2. 为什么要用递归函数
#
# 递归也是循环，而我们前面已经学了while循环，为何还要有递归呢？
#
# 简单来说就是：有些循环，递归能更简单的去实现。 #多层嵌套，更方便

#注意：
#递归要满足两个条件，一是每次回溯，规模要逐渐减少，
# 二是要有一个显性的判断条件，使递归可以结束


# 递归举例:

'''
age(5)=age(4)+2 # 注释内的内容就是下面函数干的事。
age(4)=age(3)+2
age(3)=age(2)+2
age(2)=age(1)+2
age(1)=18
age(n)=age(n-1)+2 # n>1
age(1)=18 # n=1
'''
# def age(n):
# if n == 1:
# return 18
# return age(n - 1) + 2 # 这就是回溯的思想,在它满足条件时，进入回溯过程
# 每次回溯，规模在减小，当等于1时，结束回溯过程，开始递推过程。
# # 这就是递归函数的两个重要条件
# res = age(5)
# print(res)

# 例1，打印嵌套的列表所有值
#a=[1,[2,[3,[4,[5,[6,[7,[8,[9]]]]]]]]]
'''
def func(item):
　　for i in item:
　　　　if type(i) is not list:
　　　　　　# print(type(i))

　　　　　　　　
　　　　　　print(i)
　　　　func(i)
func(a)
'''

#例2，波那契函数
'''
f = 0,1,1,2,3,5,8
def fib(n):
　　current = 0
　　num1,num2 = 0,1
　　while current<n:
　　　　num = num1
　　　　num1,num2 = num2,num1+num2
　　　　current += 1
　　　　yield num  #生成器
　　return "done"
print(list(fib(7)))
'''