signed

QiShunwang

“诚信为本、客户至上”

每日一题 递归回顾以及递归解决列表最深嵌套层数问题(第二次考试题目三)

2021/4/26 21:39:54   来源:

递归知识点总结 及题目解析

  • 1.递归知识点介绍及简单实例
    • a.错误示范(递归必须有出口)
    • b.累加问题
    • c.阶乘问题
  • 2.斐波那切数列及改进
    • a.一般的菲波那切数列数列的实现
    • b.加了记忆的方法(利用字典储存中间结果)
    • c.利用functools里的装饰器lru_cache 添加记忆
  • 3.递归构建二叉树 以及使用递归遍历(数据结构复习)
  • *4. 爬楼梯问题(一次可以走一级,两级或者三级,爬完10个台阶有多少种走法)
    • 递归解法
    • 非递归解法
  • *5.写一个函数,传入的参数是一个列表(列表中的元素可能也是一个列表),返回传入的列表有多少层嵌套

1.递归知识点介绍及简单实例

a.错误示范(递归必须有出口)

单步循环展示链接

def func(n):
    return n+func(n-1)
func(10)

# RecursionError: maximum recursion depth exceeded

b.累加问题

单步循环展示

def func1(n):
    if n==1:
        return 1
    else:
        return n+func1(n-1)
print(func1(3))

c.阶乘问题

def func2(n):
    if n==1:
        return 1
    else:
        return n*func2(n-1)
result=func2(10)
print(result)

2.斐波那切数列及改进

a.一般的菲波那切数列数列的实现

斐波那契数列 单步执行结果

def fibo(n):
    if n<=2:
        return 1
    return fibo(n-1)+fibo(n-1)
print(fibo(5))

b.加了记忆的方法(利用字典储存中间结果)

单步执行结果

def fibo2(n):
    fibo_num={1:1,2:1}
    if n in fibo_num:
        return fibo_num[n]
    fibo_num[n]=fibo2(n-1)+fibo2(n-2)
    return fibo_num[n]
print(fibo2(5))

c.利用functools里的装饰器lru_cache 添加记忆

单步执行结果 大幅缩短执行时间(空间换时间)

import functools

@functools.lru_cache(maxsize=None)
def fibo(n):
    if n<=2:
        return 1
    return fibo(n-1)+fibo(n-1)
print(fibo(5))

3.递归构建二叉树 以及使用递归遍历(数据结构复习)

class Node:
    def __init__(self, data,lchild=None,rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    def __init__(self):
        self.ls = []  # 利用队列存储树的节点
        self.flag = 0  # 存储树根后flag置为1
        self.root = None

    # 建树
    def create_tree(self, a:list):
        while 1:
            # list中没有数据,表示建树完成
            if not len(a):
                return
            #flag 为0表示树根不存在
            if not self.flag:
                self.root = Node(a[0])
                # 将树根存入队列
                self.ls.append(self.root)
                # 树根已创建,flag置为1
                self.flag = 1
                # 剔除list中第一个已经使用的数
                a.pop(0)
            else:
                '''
                treeNode:队列中的第一个节点(该节点左右孩子不完全存在)
                添加treeNode的左右孩子,当添加treeNode的右孩子之后,
                将队列中的第一个节点出队。
                '''
                treeNode = self.ls[0]
                if not treeNode.lchild:
                    treeNode.lchild = Node(a[0])
                    self.ls.append(treeNode.lchild)
                    a.pop(0)
                else:
                    treeNode.rchild = Node(a[0])
                    self.ls.append(treeNode.rchild)
                    a.pop(0)
                    self.ls.pop(0)

    # 递归实现先序遍历
    def pre_order(self, root):
        if not root:
            return
        else:
            print(root.data)
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    # 递归实现中序遍历
    def in_order(self, root):
        if not root:
            return
        else:
            self.in_order(root.lchild)
            print(root.data)
            self.in_order(root.rchild)

    # 递归实现后续遍历
    def post_order(self, root):
        if not root:
            return
        else:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data)

# list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# tree = Tree()
# tree.create_tree(list1)
#
# tree.pre_order(tree.root)
# print()
# tree.in_order(tree.root)
# print()
# tree.post_order(tree.root)
# print()

*4. 爬楼梯问题(一次可以走一级,两级或者三级,爬完10个台阶有多少种走法)

递归解法

from functools import lru_cache


@lru_cache
def run1(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    return run1(n - 1) + run1(n - 2) + run1(n - 3)

非递归解法

def run2(n):
    a = 1
    b = 2
    c = 4
    for i in range(n - 1):
        a, b, c = b, c, a + b + c
    return a

*5.写一个函数,传入的参数是一个列表(列表中的元素可能也是一个列表),返回传入的列表有多少层嵌套

def calc_nested_level(items):
    if isinstance(items,list):
        max_level=1
        for item in items:
            curr_level=calc_nested_level(item)
            max_level=max(max_level,curr_level+1)
        return max_level
    return 0

# print(calc_nested_level([1, 2, 3]))
# print(calc_nested_level([1, [2, 3]]))
# print(calc_nested_level([1, [2, [3]]]))