将大问题转化为小问题，通过递归依次解决各个小问题
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def rev_rec(s, i, j):
if i >= j:
return
s[i], s[j] = s[j], s[i]
rev_rec(s, i + 1, j - 1)
return
rev_rec(s, 0, len(s) - 1)
return
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is not None and head.next is not None:
head_next_pair = self.swapPairs(head.next.next)
p = head.next
head.next = head_next_pair
p.next = head
head = p
return head
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
注意：此题用来训练递归思维有理论意义，但是实际上算法返回的树并不是 deep copy，多个树之间会共享子树。
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generateTrees_rec(i, j):
if i > j:
return [None]
result = []
for m in range(i, j + 1):
left = generateTrees_rec(i, m - 1)
right = generateTrees_rec(m + 1, j)
for l in left:
for r in right:
result.append(TreeNode(m, l, r))
return result
return generateTrees_rec(1, n) if n > 0 else []
递归 + 备忘录 (recursion with memorization, top-down DP)
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
class Solution:
def fib(self, N: int) -> int:
mem = [-1] * (N + 2)
mem[0], mem[1] = 0, 1
def fib_rec(n):
if mem[n] == -1:
mem[n] = fib_rec(n - 1) + fib_rec(n - 2)
return mem[n]
return fib_rec(N)