前言
作为一个算法萌新，很长一段时间总是对递归和迭代的概念含糊不清，只知道用起来都是通过循环执行代码去解决一些问题，但是对于自己用的究竟算递归还是迭代傻傻分不清楚，今天就跟大家一起来好好捋一捋
迭代与递归
概念
- 迭代
迭代时重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果
- 递归
指在函数的定义中使用函数自身的方法
- 根据返回值判断
- 根据操作节点的前后位置（二叉树相关——前序，中序，后序）
这么一看两者的区分还是很明显，通过有没有调用自身，即可判断是递归还是迭代
不过有时突然想起还是容易记混，个人从字面理解的角度出发总结一下：迭代就是一代一代执行下去，很容易与for循环关联起来；递归，归就是回到原来的地方（方法），即再次调用自身
做题
回文链表
给你一个单链表的头节点
head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。回文指结构数值具有对称性
我们常见判断一个字符串是否是回文字符串，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等
- 迭代解法
首先用迭代的思路我们就需要去遍历链表，并且由于无法取得链表的长度，我们无法使用 for 去遍历，只能用while 通过判断链表节点是否为空完成遍历，取得数值数组后，使用双指针判断数组是否对称来推断是不是回文链表
var isPalindrome = function(head) { // 使用迭代获取链表对应的数组 const list = [] let root = head while (root) { list.push(root.val) root = root.next } // 使用双指针判断数组是否对称 let left = 0 let right = list.length - 1 while(left < right) { if (list[left] != list[right]) { return false } else { left ++ right -- } } return true }; 复制代码
- 递归解法
说实话这道题用递归着实不好想，首先要能想到，虽然无法获取链表的长度，但是从后打印链表的数值我们是可以做到的
先看下面的一段代码（从最后开始往前打印）
function reverseLog(head) { if (!head) { return } reverseLog(head.next) console.log(head.val) } 复制代码
如果理解了上面的逻辑，那么这道题的递归做法就容易多了
var isPalindrome = function(head) { var tmp = head function check(head) { if (!head) { return true } const res = check(head.next) && (tmp.val == head.val) tmp = tmp.next return res } return check(head) };
