1、递归函数

在函数内部，可以调用其他函数。但是一个函数在内部调用自身，这个函数被称为递归函数。

1 def calc(n):
2     print(n)
3     if int(n/2) == 0:  #结束符
4         return n
5     return calc(int(n/2))  #调用函数自身
6 
7 m = calc(10)
8 print(‘----->‘,m)

#输出结果

10

5

2

1

-----> 1 #最后返回的值

1+2+3+4+.....+100的例子：

1 def add_to_100(n):
2     if n == 0:
3         return n
4     return n + add_to_100(n-1)
5 
6 n = add_to_100(100)
7 print(n)

#输出

5050

递归特性总结

1. 必须要有一个明确的结束条件。
2. 每次进入更深一层的递归时，问题规模相比上次递归都应该少(问题规模：比如你第1次传进的是10，第2次递归应该是9...依次越来越少，不能越来越多)。
3. 递归的效率不高，递归层次过多会导致内存溢出（在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈贞，每当函数返回，栈就会减一层栈贞。由于栈的大小不是无限的，所以递归的次数过多，会导致栈溢出）。

注：死循环递归时，最多循环执行999次，防止死机

1. 函数：是定义一段代码的执行过程
2. 函数式编程：输入是确定的，输出也是确定的

函数是Python内建支持的一种封装，我们通过把大段代码拆成函数，通过一层一层的函数调用，就可以把复杂任务分解成简单的任务，这种分解可以称之为面向过程的程序设计。函数就是面向过程的程序设计的基本单元。

　　函数式编程中的函数这个术语不是指计算机中的函数（实际上是Subroutine），而是指数学中的函数，即自变量的映射。也就是说一个函数的值仅决定于函数参数的值，不依赖其他状态。比如sqrt(x)函数计算x的平方根，只要x不变，不论什么时候调用，调用几次，值都是不变的。

Python对函数式编程提供部分支持。由于Python允许使用变量，因此，Python不是纯函数式编程语言。

"函数式编程"是一种"编程范式"（programming paradigm），也就是如何编写程序的方法论。主要思想是把运算过程尽量写成一系列嵌套的函数调用。举例来说，现在有这样一个数学表达式：

(1 + 2) * 3 – 4

传统的过程式编程，可能这样写：

var a = 1 + 2;

var b = a * 3;

var c = b - 4;

函数式编程要求使用函数，我们可以把运算过程定义为不同的函数，然后写成下面这样：

var result = subtract(multiply(add(1,2), 3), 4);

这段代码再演进以下，可以变成这样

add(1,2).multiply(3).subtract(4)

day03-递归函数、函数式编程