LeetCode算法—递归

一：递归

1、定义：函数直接或者间接的调用自己

2、四个要素

（1）接受的参数

（2）返回的值

（3）终止条件

（4）如何拆解

二：LeetCode

509 斐波那契数列

def func(n):if n<2:return nelse:return func(n-1)+func(n-2)n=int(input())
print(func(n))

206 反转链表

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def reverseList(self, head: ListNode) -> ListNode:# 基准条件：空链表或者只有一个节点的链表if not head or not head.next:return head# 递归反转子链表new_head = self.reverseList(head.next)# 将当前节点连接到反转后的子链表末尾head.next.next = headhead.next = None# 返回新的头节点return new_head

344 反转字符串

#方法1 切片法
#方法2 双指针
# class Solution:
#     def func(self,s):
#         left,right=0,len(s)-1
#         while left<=right:
#             s[left],s[right]=s[right],s[left]
#             left+=1
#             right-=1
#         return s
#方法3 递归的方法
class Solution:def reverseString(self, s: List[str], left: int = 0, right: int = None) -> None:if right is None:right = len(s) - 1# 基本条件：当左指针不再小于右指针时，停止递归if left >= right:return# 交换左右指针所指的元素s[left], s[right] = s[right], s[left]# 递归处理下一个子数组self.reverseString(s, left + 1, right - 1)