递归[1]：直观的感受是与归纳法相似。必须要有的两个部分：递归基、递归规则。
- 递归基保证递归能返回结果。
- 递归规则使得问题规模减少，即保证抵达递归基。
某社区，对于递归的有趣讨论[2]。
以下的编程题，本文作者通过建立图模型，对图采用深度优先搜索，同时做适当的剪枝解决的。由于python3对输出的限制，因此对结果做了处理。
关于具体的算法实现
# PAT中的基础编程题目集函数题7-37
def dec(x, ans, seq): # x是当前待分解的整数；ans是所有分解情况；seq是当前分解结果
if x == 1: # 递归基
seq.append('1')
ans.append(seq[: ]) # copy a list
seq.pop()
else :
for i in range(1, x):
if len(seq) > 0 and int(seq[-1]) > i: # 剪枝，避免2+3+2出现
continue
seq.append(str(i))
if int(seq[-1]) > x - i: # 剪枝，保证分解项递增，避免6+1出现
seq.pop()
continue
dec(x - i, ans, seq)
seq.pop()
seq.append(str(x)) # 考虑本身也是一个分解
ans.append(seq[: ])
seq.pop()
n = eval(input())
ans = []
inans = cnt = 0
pattern = str(n) + '='
dec(n, ans, seq = [])
for equ in ans: # 该循环用于控制输出
cnt += 1
inans += 1
inequ = 0
for i in equ:
if inequ:
pattern += '+'
pattern += i
inequ += 1
if cnt % 4 == 0:
print(pattern)
pattern = str(n) + '='
cnt = 0
elif inans != len(ans) :
pattern += ';' + str(n) + '='
if cnt:
print(pattern)
