Recursion

算法
785 词

Definition

image.png

Mutiplication - Recursion

image.png

Mutiplication - iteration

image.png

Observation

image.png

类比思路

image.png

TOWERS OF HANOI

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def tower(n,fro,to,spare):

    if n==1:

        print("from %c to %c" % (fro,to))

    else:

        tower(n-1,fro,spare,to)

        tower(1,fro,to,spare)

        tower(n-1,spare,to,fro)

# 测试汉诺塔函数

tower(3, 'A', 'B', 'C')

fro:起点
to：终点
spare：空闲的柱子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def permuation(num):

    res=[]

    def backtrack(start):

        if start==len(num):

            res.append(num[:])

        else:

            for i in range(start,len(num)):

                num[i],num[start]=num[start],num[i]

                backtrack(start+1)

                num[start],num[i]=num[i],num[start]

    backtrack(0)

    return res

# 测试全排列函数

print(permuation([1,2,3]))

  • 交换 (nums[start], nums[i]) → 把候选数字放到当前 start 位置。

  • 递归 (backtrack(start+1)) → 继续处理后续位置。

  • base case (start == len(nums)) → 所有位置确定，保存结果。

  • 回溯 (swap 回去) → 撤销选择，还原数组，继续尝试别的数字。