数据结构和算法----递归
程序员文章站
2024-03-16 16:13:46
...
递归
- 递归的定义
递归,就是在运行的过程中调用自己。递归函数的优点是定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。
- 递归的限制
1、递归就是方法里调用自身。
2、在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
3、递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。
三、python中递归的缺陷
函数调用是通过栈这种数据结构来实现的,每当函数调用一次,栈就会加一层栈帧,每当函数返回栈就会减一层栈帧。由于栈的大小不是无限的,所以递归调用的次数过多,就会导致栈溢出。
解决递归栈溢出的方法就是通过尾递归优化,尾递归是指,在函数返回的时候,调用自身,如阶乘
def test(num, product): if num == 1
return product
return test(num - 1, num * product)
由于递归在方法的末尾,所以局部变量已经毫无用处,编译器可以将其“复用”,并把递归优化成循环的方式。这样的话无论递归调用多少次,都只占用一个栈帧,不会出现栈溢出现象。
遗憾的时python解释器并没有对尾递归做优化,所有python中的任何递归函数都存在栈溢出的问题
- 代码实现
此代码缺陷很多,个人能力有限。如果有好的优化方法,或者其他实现方法希望分享谢谢!
#-*- encoding:utf-8 -*-
import copy
import json
import re
import time
import uuid
from .Mysql_data import *
global dic
"""简单的递归方法就不写了,以下代码是我在数据转换中json数据转换成关系型数据。
因客户的json数据的不确定性,所以需要一个通用的模型对各类json数据进行解析。
以下我用了多个递归实现json数据的提取,主要分为两个部分,一个是提取结构,一个是提取数据。
因为是项目代码所以不能发布完整代码,直截取了递归的部分。希望大家能看明白。"""
class json_d():
def __init__(self,host,user,password,db,action_type,port):
self.uid = ""
self.dic = {}
self.dik = {}
self.dit = {}
self.host = host
self.user =user
self.password = password
self.db = db
self.action_type = action_type
self.port = port
self.is_list = "no"
self.table_jie = {}
self.a=""
self.conn = pymysql.Connect(host=host,user=user,passwd=password,db=db,port=port)
self.cursor = self.conn.cursor()
#提取表结构
def test(self,data_json, old_key ,r2,rl,depath ):
if isinstance(data_json, dict) and len(data_json.keys()) > 100:
raise RuntimeError("more_key:%s"%r2)
if isinstance(data_json, list) and data_json != [] and isinstance(data_json[0],dict) :
for da in data_json:
self.test(da,old_key, r2, rl, depath)
else:
if isinstance(data_json, dict) and len(data_json.keys()) < 100:
for key in data_json:
self.test(data_json[key], r2, key, rl, depath + 1)
else:
rl.append(old_key + "_*_" + r2 + "_*_" + str(depath))
"""以下方法是对json数据进行提取"""
def test_d(self, data_json,key,old_key,depath):
self.test_data(data_json, key,old_key,depath)
self.test_da(data_json, key,old_key,depath)
def test_da(self,data_json,key,old_key,depath):
if self.is_list == "yes":
if isinstance(data_json, list) and data_json != [] and isinstance(data_json[0], dict):
for da in data_json:
self.test_dat(da,key,old_key,depath)
dicthree = dict(self.dik, **self.dit)
if self.dit != {}:
uid = uuid.uuid1()
dicthree["uuid_id"]= str(uid)
self.table_clo = copy.deepcopy(dicthree)
for ke in self.table_jie:
dia = copy.deepcopy(dict([(key11,self.table_clo[key11]if key11 in self.table_clo.keys() else 'null') for key11 in self.table_jie[ke]]))
sql = "insert into " + ke + str(tuple(dia.keys())).replace("\'", "`") + " values " + str(tuple((str(x) for x in dia.values())))
self.cursor.execute(sql)
self.conn.commit()
self.table_clo = {}
self.dit = {}
if isinstance(data_json, dict):
for key1 in data_json:
self.test_da(data_json[key1], key1, key, depath+1)
else:
for ke in self.table_jie:
dia = copy.deepcopy(dict(
[(key11, self.dik[key11] if key11 in self.dik.keys() else 'null') for key11 in
self.table_jie[ke]]))
sql = "insert into " + ke + str(tuple(dia.keys())).replace("\'", "`") + " values " + str(
tuple((str(x) for x in dia.values())))
self.cursor.execute(sql)
self.conn.commit()
def test_das(self, data_json, key, old_key, depath):
if isinstance(data_json, list) and data_json != [] and isinstance(data_json[0], dict):
for da in data_json:
self.test_dat(da, key, old_key, depath+1)
if isinstance(data_json, dict):
for key1 in data_json:
self.test_da(data_json[key1], key1, key, depath+1)
def test_dat(self,data_json,key,old_key,depath):
if isinstance(data_json, dict):
for key1 in data_json:
self.test_dat(data_json[key1],key1,key,depath+1)
elif isinstance(data_json, list) and data_json != [] and isinstance(data_json[0], dict):
self.test_das(data_json,old_key,key,depath)
else:
self.dit[old_key+ "_*_"+key+ "_*_"+str(depath)] = data_json
def test_data(self,data_json,key,old_key,depath):
if isinstance(data_json, dict):
for key1 in data_json:
self.test_data(data_json[key1],key1,key,depath+1)
elif isinstance(data_json, list) and data_json != [] and isinstance(data_json[0], dict):
self.is_list = "yes"
else:
self.dik[old_key+ "_*_"+key+ "_*_"+str(depath)] = data_json