递归与非递归python

面试题中很多都涉及到递归与非递归&＃xff0c;比如二分法&＃xff0c;冒泡&＃xff0c;归并&＃xff0c;快排&＃xff0c;二叉树前中后遍历等等&＃xff0c;建议能直接给出非递归形式&＃xff0c;如果面试官想要看到递归形式也能熟练的写出来。

典型的面试题比如说&＃xff1a;汉诺塔问题&＃xff0c;斐波那契数列等

递归是什么&＃xff1f;和循环的区别

答&＃xff1a;

递归从字面意思理解是自己调用自己&＃xff0c;实际上递归是将问题逐渐分解减小&＃xff0c;但是和原问题有着相同解法的问题&＃xff0c;并且存在一个问题的出口。

循环就是重复执行同一段代码

打一个比方吧&＃xff0c;从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚&＃xff0c;老和尚对小和尚说&＃xff0c;从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚&＃xff0c;老和尚对小和尚说&＃xff0c;从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚&＃xff0c;老和尚对小和尚说...... 这就是递归&＃xff0c;循环就是 从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚。从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚。从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚。从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚。从前有座山&＃xff0c;山里有座庙&＃xff0c;庙里有个老和尚和小和尚。

循环和递归存在相似性但是存在本质的不同&＃xff0c;比如都是重复操作&＃xff0c;但是循环是一次正向的过程&＃xff0c;递归却需要回溯。

理论上所有的递归都可以变成非递归形式&＃xff0c;比如使用栈和循环。但是循环却不能改成递归

尾递归优化&＃xff1a;

一些语言在编译或者解释的时候能够自动对尾递归形式进行优化&＃xff0c;但是python并不能&＃xff0c;所以在python中将递归改成尾递归形式仍然不能改变递归的效率差和爆栈的问题。

针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的&＃xff0c;没有循环语句的编程语言只能通过尾递归实现循环。

递归效率低的原因&＃xff1a;

递归的简单理解&＃xff1a;

递归就是自己调用自己&＃xff0c;

递归的总结&＃xff1a;

• 找到递归出口(终止递归的条件)
• 找出递归表达式(规律)

下面这个就是用递归的方式计算阶乘

首先是递归的出口 n &＃61; 1

递归表达式 fact(n) &＃61; n * fact(n-1)

&＃61;&＃61;&＃61;> fact(5)
&＃61;&＃61;&＃61;> 5 * fact(4)
&＃61;&＃61;&＃61;> 5 * (4 * fact(3))
&＃61;&＃61;&＃61;> 5 * (4 * (3 * fact(2)))
&＃61;&＃61;&＃61;> 5 * (4 * (3 * (2 * fact(1))))
&＃61;&＃61;&＃61;> 5 * (4 * (3 * (2 * 1)))
&＃61;&＃61;&＃61;> 5 * (4 * (3 * 2))
&＃61;&＃61;&＃61;> 5 * (4 * 6)
&＃61;&＃61;&＃61;> 5 * 24
&＃61;&＃61;&＃61;> 120

递归的缺点&＃xff1a;

递归的缺点有两个&＃xff0c;首先是时间效率低&＃xff0c;需要一个展开和回溯的过程&＃xff0c;改成循环的方式就可以避免展开的过程&＃xff0c;其次是用栈的问题&＃xff0c;python的递归深度最大是1000&＃xff0c;win10系统是2MB大小&＃xff0c;&＃xff08;使用ulimit -a命令查看大小限制&＃xff09;&＃xff0c;受限于这两种限制&＃xff0c;使用递归就容易出现爆栈的问题。

递归改非递归&＃xff1a;

使用栈来模拟递归展开和回溯的过程&＃xff0c;可以避免爆栈的问题

在支持尾递归优化的语言中可以将递归改成尾递归的形式

漫谈递归转非递归 - 猿大白 - 博客园本文首发于我的公众号 Linux云计算网络&＃xff08;id: cloud_dev&＃xff09; &＃xff0c;专注于干货分享&＃xff0c;号内有 10T 书籍和视频资源&＃xff0c;后台回复 「1024」 即可领取&＃xff0c;欢迎大家关注&＃xff0c;二维码文末可以扫。 一&＃xff1a;递归https://www.cnblogs.com/bakari/p/5349383.html

 递归对应的一些常见算法题

题1&＃xff1a;计算n的阶乘

首先分析n的阶乘的一般形式是 f(n) &＃61; 1*2*.....*n

从中可以得到

f(1) &＃61; 1              递归的出口

f(n) &＃61; n * f(n-1)  递归的规律表达式

由此就可以得出递归的解法

def func(num):if num &＃61;&＃61; 1:return 1else:return num * func(num-1)

python语言的话因为没有尾递归优化&＃xff0c;所以不用考虑通过优化成尾递归的形式避免栈溢出&＃xff0c;不过可以通过这个了解下尾递归的事情

首先尾递归是有严格规定的&＃xff0c;不是说递归函数最后一行调用自己的函数就一定是尾递归&＃xff0c;比如这个函数最后虽然调用了自己&＃xff0c;但是它不是尾递归&＃xff0c;尾递归要求在最后return自己时不能有表达式&＃xff0c;是直接return自己

所以以上的函数为了改成尾递归的形式&＃xff0c;可以这样调整

def func(num,temp):if num &＃61;&＃61; 1:return tempelse:return func(num-1,temp * num)

以上的函数是一种尾递归优化&＃xff0c;每次调用的时候&＃xff0c;实际上已经将阶乘的值传递给了下一个值

这个函数的展开就没有回溯的过程。但是python仍有栈溢出的问题&＃xff0c;所以python中改成尾递归不如将递归直接改成非递归的形式。

当然这道题也有非递归的解法&＃xff0c;直接改成循环的形式即可&＃xff1a;

def func(num):temp &＃61; 1while(num):temp &＃61; temp * numnum &＃61; num - 1return temp

也可以强行套公式去转换成非递归形式&＃xff0c;类似这样&＃xff0c;用栈去记录每一次本来需要递归中栈记录得参数&＃xff1a;

def func(num):stack &＃61; list()while(num):stack.append(num)num &＃61; num - 1temp &＃61; 1while(stack):temp &＃61; stack.pop() * tempreturn temp