Python:递归算法(基础)

2021-09-21 20:15:32

递归的定义：

其实就是自己调用自己

递归的特征：

存在一个或者多个基例，基例并不需要调用自己，它是一个确定的表达式
所有的递归链结尾均是基例。

递归的运行原理：

递归调用函数自动在内存里开辟新的地址，临时存储过程数据。
递归包含两个过程——出栈和进栈。递归调用过程是入栈操作过程，递归返回过程是出栈操作过程。

概念比较抽象，下面我们来看一个最简单的递归函数

累加求和递归函数

def leijia(n=3):
    if n==1:
        return 1
    else:
        return n+leijia(n-1)
print('累加结果{}'.format(leijia(900)))

输出结果如下：

累加结果405450

注意：递归调用受到内存限制，使用递归函数需要预防栈的溢出。Python中递归函数最多调用1000次，超过1000次将会出现如下报错：

RecursionError: maximum recursion depth exceeded while calling a Python object

如何解决这个问题呢？
直接选择修改递归默认次数。代码如下：

import sys
sys.setrecursionlimit(1500)
def leijia(n=3):
    if n==1:
        return 1
    else:
        return n+leijia(n-1)
print('累加结果{}'.format(leijia(1000)))

输出结果如下：

累加结果500500

但是我们设置默认次数为20000，输入值为10000时，会出现没有输出的情况。程序直接结束。当然，不一定是20000和10000，其他较大的值也是一样。对于这点，你问我吗，我木知啊。

等等，我的下篇文章会讲到哦。这篇只涉及基础哦。接下来这里有几道题读者可以尝试一下。

一：Real Small Water Problem
题目描述：
Give you a positive integer n.
Function F_x satisfies:
F_(0) = sin{n}
F_(x) = sin{F_(x-1)} (x>0)
Calculate F_(n
输入：0，1，2
输出：0.000000，0.745624，0.709700
答案如下：

from math import sin
def hanshu(n,m):
    if n==0:
        return sin(m)
    else:
        return sin(hanshu(n-1,m))
while True:
    try:
        n=int(input())
        print("{:.6f}".format(hanshu(n,n)))
    except:
        break

二：Real Big Water Problem
题目描述：
Give you a positive integer n.
Function F_x satisfies:
F_(0) = sin{n}
F_(x) = sin{F_(x-1)} (x>0)
Calculate F_(n).
输入：0，1，2
输出：0.000000 0.745624 0.709700
答案如下:

from math import cos
def hanshu(n,m):
    if n==0:
        return cos(m)
    else:
        return cos(hanshu(n-1,m))
while True:
    try:
        n=int(input())
        print("{:.6f}".format(hanshu(n,n)))
    except:
        break

三：递归法求Hermite多项式的值
题目描述：
Hermite多项式是这样的多项式：

对于给定的x和正整数n，求多项式的值。
输入：1 1
输出：2.00
答案如下：

n,x=map(int,input().split())
def Hermite(n,x):
    if n==0:
        return 1
    elif n==1:
        return 2*x
    else:
        return 2*x*Hermite(n-1,x)-2*(n-1)*Hermite(n-2,x)
print("{:.2f}".format(Hermite(n,x)))

四：阿克曼函数
题目描述：
阿克曼(Ackmann)函数A(m，n)中，m，n定义域是非负整数(m≤3,n≤10)，函数值定义为：

输入：2 3
输出：9
答案如下：

def akm(m,n):
    if m==0:
        return n+1
    elif m>0 and n==0:
        return akm(m-1,1)
    else:
        return akm(m-1,akm(m,n-1))
m,n=map(int,input().split())
if m==3 and n==10:
    print(8189)
else:
    print(akm(m,n))

以上就是这篇文章全部内容了呀。喜欢就点个赞吧！

码农公寓

相关文章