Recursion

发表于 |

之前我一直对递归抱有很深的误解，还没有去了解递归是什么就对这个概念感到害怕，一遇到递归就死机。

我在知乎上看到一个问题说：“如何理解递归？”，有一条回复是：“要理解递归，先理解递归。”这样看起来确实很糊涂，所以我就更糊涂了。

最近看《Problem Solving With Algrithm and Data Structure》这本书，重新去了解了递归的概念和法则，并且从简单的练习里真正去运用递归，发现递归其实没有想的那么困难。

什么是递归？

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems. Until you get to a small problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us write elegant solution to problems that may otherwise be very diffcult to program.

简单来说，递归就是把一个问题分解成更小的问题，直到这个问题小到可以被轻易的解决。就像 1+2 这么简单。同时，递归需要调用自身来解决问题。

递归的三个法则

  • A recursive algorithm must have a base case.
  • A recursive algorithm must change its state and move toword the base case.
  • A recursive algorithm must call itself, recursively.
  • 运用递归，必须要有一个最基础的解决方法。
  • 运用递归时，必须要一直朝着基础的方法前进。意思是每一步都会把问题分解成更基础的算法，直到问题变成可以用最简单的方法解决。
  • 递归必须要调用自身。

这里是 base case 就是指一个可以直接解决的小问题。例如：1+2， 1*2 这种。

章节4.5后面有2个小的练习：

  • Write a function that takes a string as a parameter and returns a new string that is the reverse of the old string.
  • Write a function that takes a string as a parameter and returns True if the string is a palindrome, False otherwise. Remember that a string is a palindrome if it is spelled the same both forward and backward. For example: radar is a palindrome. for bonus points palindromes can also be phrases, but you need to remove the spaces and punctuation before checking. for example: madam i’m adam is a palindrome.

这2个小练习都非常简单，并且有很多种方法去写。

以下答案：

1
2
3
4
5
def reverse(s):
	if len(s) == 1:
		return s
	else:
		return reverse(s[1:]) + s[0]

第二题：

1
2
3
4
5
6
def isPalindrome(s):
	if len(s) <= 1:
		return True
	from string import ascii_letters
	s = ''.join([i.lower() for i in s if i in ascii_letters])
	return s[0] == s[-1] and isPalindrome(s[1:-1])

做完以上2个小练习之后，我对递归的概念就清楚很多了。