递归
Opened this issue · 6 comments
递归,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
递归的**就是把问题分解成为规模更小的、具有与原问题有着相同解法的问题。
是不是这样的问题都能用递归来解决呢?答案是否定的。
一般来讲,能用递归来解决的问题必须满足两个条件:
- 可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式。
- 存在一种简单情境,可以使递归在简单情境下退出。
如果一个问题不满足以上两个条件,那么它就不能用递归来解决。
所以当我们考虑使用递归解决某个问题时,首先就需要考虑是否满足递归的两个条件。
递归三大要素
第一要素:明确函数功能
例如,定义了一个函数:
function factorial(n) {}
这个函数的功能就是计算 n 的阶乘。
第二要素:寻找结束条件
例如,当 n = 1 时,factorial(1) = 1
;当n = 2时,factorial(2) = 2 * 1 = 2
,那么结束条件就可以这么写:
function factorial(n) {
if (n <= 2) {
return n;
}
}
第三要素:寻找等价关系
不断缩小参数范围(归纳),把问题蜕变成子问题的表达式(步进表达式)。
例如,factorial(n)等价为factorial(n) = n * factorial(n-1)
:
function factorial(n) {
if (n <= 2) {
return n;
}
return n * factorial(n - 1);
}
斐波那契数列
斐波那契数列:f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)。
从定义上看,显然这问题可以通过递归来解决的。
明确函数功能
function fibonacci(n) {}
寻找结束条件
function fibonacci(n) {
if (n ===0) {
return 0;
} else if (n === 1) {
return 1;
}
}
寻找等价关系
function fibonacci(n) {
if (n ===0) {
return 0;
} else if (n === 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
回文串
“回文串”是一个正读和反读都一样的字符串,例如“level” 、“noon”。
首先我们考虑递归的两个条件:
第一:这个问题是否可以分解为形式相同但规模更小的问题?
第二:如果存在这样一种分解,那么这种分解是否存在一种简单情境?
如果一个字符串是回文,那么在它的内部一定存在着更小的回文,比如level里面的eve也是回文,而且,一个回文的第一个字符和最后一个字符一定是相同的,所以我们可以得出:
先判断给定字符串的首尾字符是否相等,若相等,则判断去掉首尾字符后的字符串是否为回文,若不相等,则该字符串不是回文。
我们已经成功地把问题的规模缩小了,去掉首尾字符的字符串当然比原字符串小。
对于回文问题,我们容易发现,一个只有一个字符的字符串一定是回文,所以,只有一个字符是一个简单情境,但它不是唯一的简单情境,因为空字符串也是回文。
这样,我们就得到了回文问题的两个简单情境:字符数为1和字符数为0。
两个条件都满足了,因此我们可以使用递归来解决这个问题。
明确函数功能
// 是否是回文字符串
function isPalindrome(str) {}
寻找结束条件
function isPalindrome(str) {
if (str.length === 0 || str.length === 1) {
return true;
}
}
寻找等价关系
function isPalindrome(str) {
const len = str.length;
const first = str[0];
const last = str[str.length - 1];
console.log('Length: ', len);
console.log(first, '===========', last);
if (len === 0 || len === 1) {
return true;
}
// 如果首尾字符相同,则问题等价于求解子字符串的首尾字符是否相同
if (first === last) {
return isPalindrome(str.substring(1, str.length - 1));
}
return false;
}
求和
function sum(n)
{
if (n == 1) {
return 1; // 这个就是递归的出口,化简为非递归状况处理
} else {
return sum(n - 1) + n; // 子问题须与原始问题
}
}
示意图
反转单链表
反转单链表,例如链表为1->2->3->4,反转后为 4->3->2->1。
首先考虑原问题能否拆成更小的子问题。
对于链表来说,就是缩小链表长度,如果我们先对 2->3->4递归,其反转结果如下:
head —> 1
|
V
4 —> 3 —> 2
我们把 2->3->4 递归成 4->3->2,但节点1不变,仍然指向2。
接下来把节点2的next指向1,再把节点1的next指向null,结果如下:
null <— 1
^
|
newHead -> 4 —> 3 —> 2
然后对head为null或者header.next为null的节点,递归可以结束。
满足递归的两个条件,可以用递归来求解。
明确函数功能
function reverse(head) {}
寻找结束条件
function reverse(head) {
if (head === null || head.next === null) {
return head;
}
}
寻找等价关系
function reverse(head) {
if (head === null || head.next === null) {
return head;
}
// head.next即缩小了链表长度
let newHead = reverse(head.next);
// 节点1
let t1 = head;
// 节点2
let t2 = t1.next;
t2.next = t1;
t1.next = null;
return newHead;
}
最终结果如下:
null <— 1
^
|
newHead -> 4 —> 3 —> 2