前言
对于递归算法，我们最先想到的应该就是用递归的方式去中序遍历一棵树，递归的使用使得我们可以先深入到下层中，然后慢慢的输出下层的元素之后输出上层元素。
因此，基于此，我们甚至可以使用递归来逆序输出一个栈，链表等数据结构。
递归输出树
逆序输出栈
递归逆序输出链表
与上面逆序输出一个栈差不多，我们可以设定输出链表内容的条件，我们可以先让链表不断的向内遍历，遍历到尾节点没有下一个节点了，我们才开始输出链表的内容，那么就可以做到逆序输出链表的内容了。
public void reverseList(ListNode head){ if(head!=null){ reverseList(head.next); System.out.println(head.val); } }
基于这种方式，我们甚至可以使用递归来判断一个链表是不是回文链表。
currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。
算法的正确性在于递归处理节点的顺序是相反的（回顾上面打印的算法），而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。
计算机在递归的过程中将使用堆栈的空间，这就是为什么递归并不是 O(1) 的空间复杂度。
package com.leetcode.learn.list.easy; import com.leetcode.learn.list.ListNode; /** * @author: 张锦标 * @date: 2023/6/10 11:15 * PalindromeList类 */ public class PalindromeList { private ListNode frontPointer; private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true; } public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head); } //public boolean isPalindrome(ListNode head){ // StringBuilder sb = new StringBuilder(); // ListNode temp = head; // while(temp!=null){ // sb.append(temp.val); // temp=temp.next; // } // return sb.toString().equals(sb.reverse().toString()); //} public void reverseList(ListNode head){ if(head!=null){ reverseList(head.next); System.out.println(head.val); } } }
递归判断字符串是否是回文串
使用递归的方式，我们也可以用来判断一个字符串是否是回文串。
我们可以将字符串按照中心划分两半，使用两个指针分别指向字符串的开头和末尾然后向中间遍历。不断判断这两个指针是否相同，如果是，那么指针向中间继续移动。
package com.leetcode.learn.string; /** * @author: 张锦标 * @date: 2023/6/10 11:44 * RecusionHuiwen类 * 使用递归的方式来判断一个字符串是否是回文串 */ public class RecusionHuiwen { public static boolean isPalindrome(String s,int n,int m){ if (m<=1){ //递归结束条件 return true; }else if(s.charAt(n)==s.charAt(m-1)){ //判断当前两个对称位置是否相同 return isPalindrome(s,n+1,m-1); //相同继续向后遍历递归 } return false; } public static void main(String[] args) { String s = "abccba"; System.out.println(isPalindrome(s, 0, s.length())); } }
