尾递归和递归简析

递归：

简单的来说递归就是一个函数直接或间接地调用自身。
每个递归函数都有两个条件：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

示例代码如下: x==1就是基线条件

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

print (fact(3))

查看递归调用栈：

这里从上往下，最上边是栈底，当开始执行时，系统为变量x分配内存，然后执行代码，满足递归条件，会调用另一个fact函数，当前函数暂停，并处于未完成的状态，但该函数的变量的值还在内存中。直到栈顶的x=1那次调用返回，才依次拉起之前的函数调用，最终执行获取结果。图中最下面是栈顶，这个栈用于保存多个函数的变量，称为调用栈。

递归的缺点：

递归调用时，每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。

解决办法有两种：

• 使用循环
• 使用尾递归

递归使用场景：

(1)数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
　 (2)问题解法按递归实现。（回溯）
　 (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）

尾递归

尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。

尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。

例如：

def fact(x,y):
    if x==0:
        return y
    else :
        return fact(x-1,y+1)

print(fact(3,0))

调用栈，不会向上调用，执行到最后一次，最终结果就已经出来了，为3，没有中间的结果变量。

小结：

递归是调用自己的函数，每个递归有两个条件：基线条件和递归条件。

栈是一种数据结构，先入后出，有压入和弹出两种操作。

所有函数调用，都进入调用栈。调用栈可能很长，这将占用大量内存。