闲聊 Recursion 递归

递归的定义

维基百科定义:递归是一个物品以自我重复的方式处理问题
从算法的角度解释:递归是把一个问题划分为更小的问题,并解决这个小的问题,而且解决最开始的问题的方法。
从语义的角度解释:递归就是自己调用自己

用我自己的说法:递归就是把一个问题拆分成更简单的问题,用相同的方法实现

  • 用3D打印机一台3D打印机
  • 四周都是镜子墙

递归的前提条件

  • 需要有一个基例(base case),通常是一个表达式,当问题已经被划分到最细的粒度,返回一个表达式给上一层方法体中。
  • 需要有递归的链条,即实现把问题“缩小”的具体实现方法,直到“缩小”到基例。

case 1 阶乘

# 递归的方式实现
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)
# 递归的基例很明显是1,因为0!只会等于1
# 递归的链条:n * fact(n-1)
# 递归链条需要用相同的办法细分问题,只能比原来的表达式更小

# 循环实现
def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

递归的过程

两种方法都能实现阶乘的效果,但是哪一种更好仁者见仁智者见智,在我看来用递归的方式更加简单,明了。

观察现象

  • 每一次递归调用自己,都创造了一个新的scopeenvironment
  • scope所绑定的变量不会被递归调用给改变
  • 一旦调用了函数且返回了一个具体的值,会传递给之前调用的scope

case 2 汉诺塔问题

count = 0


def towers(n, src, des, mid):
    global count
    if n == 1:     # 当只有一个盘子的时候直接可以搬运到终点
        print("{} : {} --> {}".format(1, src, des))
        count += 1
    else:
        towers(n-1, src, mid, des) 
	# 如果上面还有盘子,使用des柱子作为一个过渡,搬运到mid柱子上
        print("{} : {} --> {}".format(n, src, des))
        count += 1
	# 搬运完 n-1 个盘子,将最后一个盘子搬运到目标柱子,count次数+1	
        towers(n-1, mid, des, src)
	# 再将之前中间的柱子上的圆盘搬运到目标柱子上

towers(3, "A", "B", "C")

case 3 回文数

回文数:正着读和反着读都是相同的字符串
eg: 上海自来水来自海上

# 回文数
def isPalindrome(s):
    s = s.lower()
    l = len(s)

    if l < 2:
        return True
    elif s[0] == s[l - 1]:
        return isPalindrome(s[1 : l - 1])
    else:
        return False


s = "MalaYaLam"
ans = isPalindrome(s)

if ans:
    print("Yes")

else:
    print("No")


print(isPalindrome("madam"))

case 4 快速排序

def quick_sort(lists, i, j):
    if i >= j:
        return list
    pivot = lists[i]
    low = i
    high = j
    while i < j:
        while i < j and lists[j] >= pivot:
            j -= 1
        lists[i] = lists[j]
        while i < j and lists[i] <= pivot:
            i += 1
        lists[j] = lists[i]
    lists[j] = pivot
    quick_sort(lists, low, i-1)
    quick_sort(lists, i+1, high)
    return lists


lists = [30, 24, 5, 58, 18, 36, 12, 42, 39]
print("排序前的序列为:")
for i in lists:
    print(i, end=" ")
print("\n排序后的序列为:")
for i in quick_sort(lists, 0, len(lists)-1):
    print(i, end=" ")

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×