递归
 
递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。
 
注:
 递归的时候，每次调用一个函数，计算机都会为这个函数分配新的空间，这就是说，当被调函数返回的时候，调用函数中的变量依然会保持原先的值，否则也不可能实现反向输出。
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//递归
void test(int num)
{
	if (num == 1)
	{
		printf("%d\n", num);
		return;//终端函数很重要
	}
	test(num - 1);
	printf("%d\n", num);
}
int main()
{
	test(3);
	printf("main\n");
	return 0;
}
 
输出结果：123
 
 字符串逆序输出
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//利用递归实现字符串的逆序输出
void test(const char *str)
{
	if (*str == '\0')//比较的是字符串是否等于\0
		return;
	test(str + 1);
	printf("%c\n", *str);//每次打印字符串中第一个字符
}
int main()
{
	test("happy end");
	printf("\n");
	return 0;
}
 
 
斐波那契数列：前两项之和等于第三项
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//斐波那契数列 1 1 2 3 5 8 13 21 34 55....
int test(int num)
{
	if (num == 1 || num == 2)
		return 1;
	else
		return test(num - 1) + test(num-2);
}
int main()
{
	printf("%d", test(10));
	printf("\n");
	return 0;
}
 
 
阶乘
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//阶乘：n表示 阶乘 乘到几
int test(int num)
{
	if (num <= 0)
	{
		printf("输入有误");
		return 0;
	}
	if ( num == 1)
		return 1;
	return test(num - 1) * num;
}
int main()
{
	printf("%d", test(5));
	printf("\n");
	return 0;
}
 

 
 
 
特点：
 
递归函数特点
 
每一级函数调用时都有自己的变量，但是函数代码并不会得到复制，如计算5的阶乘时每递推一次变量都不同；
每次调用都会有一次返回，如计算5的阶乘时每递推一次都返回进行下一次；
递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；
递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；
递归函数中必须有终止语句。
 
效率
 
1.系统栈（也叫核心栈、内核栈）
 是内存中属于操作系统空间的一块区域，其主要用途为： (1)中断现场，对于嵌套中断，被中断程序的现场信息依次压入系统栈，中断返回时逆序弹出； (2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
 
2.用户栈
 是用户进程空间中的一块区域，用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
 我们编写的递归程序属于用户程序，因此使用的是用户栈。
 
3.栈溢出
 函数调用的参数是通过栈空间来传递的，在调用过程中会占用线程的栈资源。而递归调用，只有走到最后的结束点后函数才能依次退出，而未到达最后的结束点之前，占用的栈空间一直没有释放，如果递归调用次数过多，就可能导致占用的栈资源超过线程的最大值，从而导致栈溢出，导致程序的异常退出。
 
综上:
 函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N次局部变量、N次形参、N次调用函数地址、N次返回值,势必效率低.
 
优点
 
1.代码简洁、清晰,易懂
 
对于我们,能用循环解决的,尽量不适用递归.
 下面是实际使用递归解题的模板和技巧
 轻松学会递归秒杀题目

 
关于递归函数转换非递归函数的一些方式
 
前言
目的
可行性
转换的几种途径
  
转换示例
第一个例子：阶乘n!
第二个例子：菲波那契数列
效率的比较
1、阶乘三种方式函数的执行效率比较
2、Fibonacci三种方式函数的执行效率比较
  
  
总结
说明
调试的方法
完整的代码
 

 
前言
 
最近在重拾算法和数据结构的一些知识，打算从基本的树的遍历算法入手。网上翻看了很多的二叉树的遍历算法相关文章，二叉树的遍历有前、中、后三种遍历方法。最简单的用递归方法遍历，三种方法的逻辑一目了然很好理解，看到非递归遍历方法时，前序遍历还能理解，中序和后序遍历看的理解起来感觉不那么顺了，所以想先研究一下递归方法改非递归方法的一些方法，翻看了一些文章结合自己的理解记录下对递归方法改成非递归方法的一些方法。
 
目的
 
既然是要将递归方法转换成非递归方法，那首先就要明白为什么要将递归方法转换成非递归方法，也就是递归转非递归的目的和意义何在？如果这样的转换没有任何实际意义那也就不存在转换的必要了。下面收集了一些递归和非递归方法的一些优缺点，自己权衡：
 
递归函数逻辑清楚，以数学化的方式来写函数，便于理解。非递归函数一般相对逻辑性和可理解性要差些。
大部分语言的编译器对递归的层数有限制。非递归函数没有这个限制。当然有时间和性能上的要求。
递归方式使用了系统的栈来存储函数的参数和变量等，造成额外的更多的开销。 非递归方式要分情况考虑系统开销，后面例子测试会有比较。
 
可行性
 
既然清楚了递归函数转换成非递归函数的目的，下面就要提出一个问题，那就是是否所有的递归函数都能转换成非递归函数即转换的可行性。这个答案是肯定的。一个显然的原因是：我们计算机是如何运行递归函数的？学习过汇编语言的童鞋可以很自然的理解这个原因。汇编语言中对函数的调用通过call指令来执行， call指令通过将调用程序段执行的寄存器及代码执行计数器入栈的方式来执行被调用函数，被调用函数执行完毕后通过return指令来出栈。所以原则上我们可以借助栈这个结构用程序来模拟函数调用过程，也就是可以实现非递归转换成递归的方法。
 
转换的几种途径
 
递归转换成非递归一般有以下几种途径：
 
可行性里面介绍了借助栈来实现转换。
使用循环和数组方式来转换。
 
这两种方法效率不同，且循环数组方式不一定能解决所有的转换问题，查阅网上的一些资料可以参考：
 
公众号：Linux云计算网络的 : 漫谈递归转非递归.
奔跑de五花肉的： 递归算法转换为非递归算法的技巧.
 
转换示例
 
第一个例子：阶乘n!
 
由易入难首先选择阶乘，n的阶乘计算方法： n! = n * (n-1) * (n-2) * … * 3 * 2 * 1 (n>0且n属于自然数)，它也可以是一个最简单的递归函数，假设f(n)=n!，则f(n)=n * f(n-1)，f(1) = 1，那么写成递归代码如下（本文代码均用Python描述）：
 
# 递归求阶乘 n>0
def recu_fact(n):
	if n==1:
		return 1
	else:
		return n * recu_fact(n-1)
 
这个递归函数就是尾递归函数，我们可以很自然的使用循环来改写成非递归结构，代码如下：
 
# 非递归方式求阶乘，循环数组方法改写
def cycle_fact(n):
	result = 1
	for i in range(1, n+1):
		result = result * i
	return result
 
然后，我们用栈模拟方式来改写成非递归结构，python中的list有append()和pop()方法实际上可以看成栈，但是为了便于理解，我们先定义一个文件stack.py来模拟一个栈类，代码如下：
 
#!/usr/bin/python
# coding:utf-8
# stack.py
# 使用列表封装的一个简易Stack类，便于演示算法

class Stack(object):
	def __init__(self):
		self._list = []
	
	# 压栈	
	def push(self, node):
		self._list.append(node)
	
	# 出栈
	def pop(self):
		return self._list.pop()
	
	# 栈是否为空
	def empty(self):
		return len(self._list) == 0
	
	# 栈顶元素	
	def top(self):
		return self._list[-1]
	
	def __len__(self):
		return len(self._list)
 
push(), pop(),empty(),top()是栈常用的几个方法，不多解释。
 然后尝试用栈模拟来变更成非递归方法，代码如下：
 
# 非递归阶乘计算
# n>0; n=1:f(1)=1, n>1:f(n)=n*f(n-1)
# 理解last和top指针的作用，cmp(last,top)决定是压栈还是出栈		
def nonrecu_fact(n):
	# 定义一个类来存储函数的参数和返回值
	class ret(object):
		n = 0			# 函数参数
		result = None		# 函数返回值
		def __init__(self, n):
			self.n = n
	#pdb.set_trace()
	stack = Stack()
	r = ret(n)
	stack.push(r)	
	last = r	# 每一次push的时候要设置last为栈顶元素
	while not stack.empty():
		top = stack.top()
		if top.n == 1:
			top.result = 1
			last = stack.pop()	# 每一次pop要设置last，pop意味着栈顶函数已经解出
		else:
			if last == top:	# 两者一致说明上一层的函数未解出，所以需要压栈
				r = ret(top.n-1)
				stack.push(r)
				last = r
			else:
				m = last.result
				top.result = m * top.n
				last = stack.pop()
	return last.result
 
这里解释下：
 
建立类ret主要用来保存函数的参数和返回值，可以想象一下函数调用过程，函数参数如何传给调用函数，返回值又如何提供给调用函数。
循环的结束靠栈是否为空判断。
循环外栈中压入第一个对象。
通过last和top指针的比较来判断是压栈还是出栈。
 
第二个例子：菲波那契数列
 
斐波那契数列又叫兔子数列，它的由来和那个经典的数学题有关：每对大兔每个月能生产1对小兔，而每对大兔生长2个月就成为大兔，假设初始只有1对小兔，求n个月后兔子的对数。数学表示：n个月兔子的对数为F(n)，则F(n)=F(n-1)+F(n-2)，显然F(1)=F(2)=1，这就是Fibonacci数列的公式。递归函数求解逻辑很自然，代码如下：
 
# 递归fibonacci数 n>0 
def recu_fib(n):
	if n<=2:
		return 1
	else:
		return recu_fib(n-1) + recu_fib(n-2)
 
下面寻找转换为非递归的方法，首先考虑循环数组方式，代码如下：
 
# 非递归计算fibonacci数列，循环数组方式
def cycle_fib(n):
	x = [1] * n
	for i,value in enumerate(x):
		if i>=2:
			x[i] = x[i-1] + x[i-2]
	return x[-1]
 
使用栈模拟方式转换，代码如下：
 
# 非递归计算fibnacci数列，栈模拟方式
def nonrecu_fib(n):
	# 定义类存储函数的参数和返回值
	class ret(object):
		n = 0,		# 存储形参
		n1 = None	# 内部变量，存储f(n-1)
		n2 = None	# 内部变量，存储f(n-2)
		result = None	# 存储返回值
		def __init__(self, n):
			self.n = n

	stack = Stack()
	r = ret(n)
	stack.push(r)
	last = r	
	while not stack.empty():
		top = stack.top()
		if top.n in (1,2):
			top.result = 1
			last = stack.pop()
		else:
			if last == top:	
				if top.n1 == None:		# top.f(n-1)还未算出，继续push下一层
					r = ret(top.n-1)
					stack.push(r)
					last = r
				else:					# top.f(n-1)已解出，开始计算top.f(n-2), push f(n-2)
					r = ret(top.n-2)
					stack.push(r)
					last = r
			else:
				m = last.result
				if top.n1 == None:
					top.n1 = m
					last = top	# 此处一定要设置last和top一致
				else:
					top.n2 = m
					top.result = top.n1 + top.n2
					last = stack.pop()
	return last.result
 
效率的比较
 
1、阶乘三种方式函数的执行效率比较
 
首先比较阶乘的三种方式所用的时间，代码如下：
 
# 导入时间模块用于计算程序运行时间
import time	
def main():
	t0 = time.clock()
	f1 = [recu_fact(i) for i in range(1, 15)]
	t1 = time.clock()
	f2 = [cycle_fact(i) for i in range(1, 15)]
	t2 = time.clock()
	f3 = [nonrecu_fact(i) for i in range(1, 15)]
	t3 = time.clock()
	print(f1)
	print(f2)
	print(f3)
	print('recu method: %fms'%((t1-t0)*1000))
	print('cycle method: %fms'%((t2-t1)*1000))
	print('nonrecu method: %fms'%((t3-t2)*1000))
 
在开始测试前，我预估了一下结果应该是：数组循环方式最快，递归和栈模拟方式最慢，但是两则时间应该差不多。但是 结果打脸了，😓 调用main函数，实际运行结果如下：
 
 运行时间：循环数组方式<递归<栈模拟。 最让我觉得不可思议的地方是栈模拟方式慢了那么多。会不会是巧合？多次运行后结果差不多，改代码全部运行F(i)(i取值100，200，300等)也是如此，单次运行大概栈模拟的时间大概是递归时间的4-2倍左右，运行时间次数越多，越趋向于2倍，递归是循环数组方式的6倍左右。修改代码并使用matplolib画图，代码如下：
 
# 导入时间模块用于计算程序运行时间
import time	

# 导入matplotlib和numpy用于画图
import matplotlib.pyplot as plt
import numpy as np
def main():
	x = np.linspace(100,900,9)
	y1 = []
	y2 = []
	for i in x:
		i = int(i)
		t0 = time.clock()
		f1 = recu_fact(i)	
		t1 = time.clock()
		f2 = cycle_fact(i)	
		t2 = time.clock()
		f3 = nonrecu_fact(i)	
		t3 = time.clock()
		
		e1 = (t1-t0)*1000
		e2 = (t2-t1)*1000
		e3 = (t3-t2)*1000
		print(i, e1, e2, e3)
		y1.append(e1/e2) 	# 以循环数组方式运行时间为基准，递归相对于循环数组的花费时间
		y2.append(e3/e2)	# 以循环数组方式运行时间为基准，栈模拟相对于循环数组的花费时间
	
	plt.plot(x,y1)
	plt.plot(x,y2)
	plt.show()
 
运行结果如下：
 
 X轴是F(x)中的x取值，取了100，900之间每隔100的9个离散值，黄线是以循环数组方式运行耗费时间为基准，栈模拟方式运行时间耗费，蓝色的线是以循环数组方式运行耗费时间为基准，递归方式运行时间耗费。由于python对递归深度的默认限制大概是998次，所以没有计算F(1000)以后的情况了。从图中看，黄色线是逼近蓝色线的，我猜测之所以造成用栈模拟方式花费时间比递归时间高这么多的原因在于python编译器对递归的优化比我手工使用列表栈的方式更优化。此测试也可以看出，系统对递归函数的调用深度有限制。但是使用栈模拟的方式确没有这个限制，只要机器的运行速度和内存可以跟的上的话，例如调用recu_fact(1000)会报递归深度超过最大值错误，我的电脑调用nonrecu_fact(2000)确没有任何问题。当然，还有另外一种方式修改python的默认递归深度的最大值的方式，这不细说了。
 
2、Fibonacci三种方式函数的执行效率比较
 
其实结果应该和第一点的运行效率比较结果大致一致，这里不多说了，直接放测试代码如下：
 
# 导入时间模块用于计算程序运行时间
import time	
def main():
	
	t0 = time.clock()
	g1 = [cycle_fib(i) for i in range(1, 30)]
	t1 = time.clock()
	g2 = [recu_fib(i) for i in range(1, 30)]
	t2 = time.clock()
	g3 = [nonrecu_fib(i) for i in range(1, 30)]
	t3 = time.clock()
	print(g1)
	print(g2)
	print(g3)
		
	print('cycle method: %fms'%((t1-t0)*1000))
	print('recu method: %fms'%((t2-t1)*1000))
	print('nonrecu method: %fms'%((t3-t2)*1000))
 
运行结果如下：
 
 以上比较结果更显著，不多说。
 
总结
 
从上面的测试及分析可以看出：
 
循环数组方式转换递归方法效率最高，这其实是一种空间换时间的方法，但是，并不适合所有的递归转换。
递归方式简单明了，逻辑清楚，但是一般语言的编译器对递归深度有限制。
栈模拟的方式转换递归，可以转换所有的递归，这其实是一种使用栈结构来模拟底层函数调用的一种实现。但是也存在逻辑上不够清楚的缺陷，但是能绕过一般语言编译器上对递归深度的限制。效率上没有编译器的优化，效率最差。
 
所以用不用递归，应该视具体问题而言，各种选择都有优劣。在循环数组方式逻辑清楚的情况下用循环数组方式其实更好的照顾了执行效率和代码的可读性。 如果在必须用递归的情况下，尽可能的使用一种叫尾递归的方法改造递归函数，尾递归其实是在递归函数的一种优化的表示，原则上可以使用更少的栈空间，但是可读性上也要稍差，可以参考下面对尾递归的介绍：
 怀念小兔： 递归和尾递归.
 
说明
 
调试的方法
 
python程序测试过程中都会用到调试，使用最多的可能是打印日志的方法，但是使用pdb调试效率会更高，例如本篇，我为了测试递归函数和我写的栈模拟的区别使用了pdb调试，pdb调试一般有两种方法：
 
cmd下加载代码，命令：python -m pdb recursive.py 进入pdb后设置断点等。
在程序中import pdb，在需要设置断点的地方使用：pdb.set_trace()
 单步调试指令n,进入函数s. 百度搜索"python pdb"等可以得到更多指令，不细说。
 
完整的代码
 
完整的测试代码见本文附件资源。

Python递归函数！
 
 
今天博主跟大家聊一聊如何使用Python递归函数！不喜勿喷，如有建议欢迎补充、讨论！
 
关于安装和汉化可以观看博主的这篇文章《下载安装及汉化 》以及Python系列：windows10配置Python3.0开发环境！，安装完毕重启VsCode！以及VSCode配置Python开发环境！
 
 
Come on！什么是递归：
 
 
 
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。记住哦->在函数内部调用其他函数不是函数的嵌套，而在函数内部定义子函数才是函数的嵌套。
 
 
递归的特性：
 
 
递归函数必须有一个明确的结束条件。
 
 
每进入更深一层的递归时，问题规模相对于上一次递归都应减少
 
 
相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
 
 
递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。
 
 
例如下面的案例
 
'''
@Descripttion: 这是一个文件头注释！
@version: 1.0.0
@Company: DCIT-SH
@Author: Sunny Chen
@Date: 2019-10-09 18:20:20
@LastEditors: Sunny Chen
@LastEditTime: 2019-10-15 09:58:20
'''

import sys
#通过循环来实现叠加
def sum1(n):
    '''
to n,The sum function
    '''
    sum = 0
    for i in range(1,n + 1):
        sum += i
    return sum

#通过函数的递归来实现叠加
def sum2(n):
    '''
to n,The sum function
    '''
    if n > 0:
        return n + sum2(n - 1) #调用函数自身
    else:
        return 0

print("循环叠加-->",sum1(50))
print("递归叠加-->",sum2(50))

#两者实现的效果均是：1275
 
两者都可以实现叠加的效果。后者相对前者有什么优缺点？
 
 
递归函数有啥优缺点：
 
 
 
递归函数的优点：定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。
 
 递归函数的缺点：使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。
 
 把上面的递归求和函数的参数改成10000就导致栈溢出！
 
 当然也可以通过尾递归来对递归的栈溢出进行优化。这里就不详细介绍了。请参考(Python开启尾递归优化!)：http://www.open-open.com/lib/view/open1480494663229.html
 
 
 
通过实例来介绍函数递归：
 
'''
@Descripttion: 这是一个文件头注释！
@version: 1.0.0
@Company: DCIT-SH
@Author: Sunny Chen
@Date: 2019-10-09 18:20:20
@LastEditors: Sunny Chen
@LastEditTime: 2019-10-15 10:20:37
'''

# 假如街上有这么一群人，我想问知道长沙的小吃街在哪。其中只有二狗子（大吃货）知道在哪。
names = ["小佳佳", "刘二", "张三", "李四", "二狗子", "王五"]
print(names)
# 问路

def ask_way(lis):
    # 街上就我一个人的情况下
    if len(lis) == 1:
        return "没有人知道这个地方在哪。"
    # 街上不只我一个人的情况下，先问第一个人
    name = lis.pop(0)
    # 如果这个人是二狗子，那么问到路，递归结束
    if name == "二狗子":
        return "二狗子说：长沙的小吃街在天心区南门口！！"
    # 如果这个人不知道路，就去问下一个人，下一个人就好把结果告诉这个人。
    print("<%s>问：你[%s]好，请问你知道长沙的小吃街在哪吗？" % (name, lis[0]))
    print("不好意思，我帮您问一下%s,他可能会知道！！\n" % lis[0])
    res = ask_way(lis)
    if name != "小佳佳":
        print("<%s>说：%s" % (name, res))
    return res

ask_way(names)

# 输出结果为：
"""
['小佳佳', '刘二', '张三', '李四', '二狗子', '王五']
<小佳佳>问：你[刘二]好，请问你知道长沙的小吃街在哪吗？
不好意思，我帮您问一下刘二,他可能会知道！！

<刘二>问：你[张三]好，请问你知道长沙的小吃街在哪吗？
不好意思，我帮您问一下张三,他可能会知道！！

<张三>问：你[李四]好，请问你知道长沙的小吃街在哪吗？
不好意思，我帮您问一下李四,他可能会知道！！

<李四>问：你[二狗子]好，请问你知道长沙的小吃街在哪吗？
不好意思，我帮您问一下二狗子,他可能会知道！！

<李四>说：二狗子说：长沙的小吃街在天心区南门口！！
<张三>说：二狗子说：长沙的小吃街在天心区南门口！！
<刘二>说：二狗子说：长沙的小吃街在天心区南门口！！
"""
 
递归值返回时返回到上一层，而其他的层在执行的过程中，均在等待答案。快去动手试试吧！
 
 
到这里:Python递归函数！分享完毕了，快去试试吧！
 
 
最后
 
 
更多参考精彩博文请看这里：陈永佳的博客
 
 
喜欢博主的小伙伴可以加个关注、点个赞哦，持续更新嘿嘿！