Recursion
Contents
Introduction
Recursion is when a function repeatedly calls itself. Defining a recursive function generally involves two steps: identifying the base case and finding the recursive relation. Articles introducing recursion usually begin with the Fibonacci sequence and calculating A!. Slightly more advanced discussions cover the Tower of Hanoi and the eight queens problem. They then discuss time and space complexity. Tracing the call stack reveals many repeated recursive calls, leading to improvements such as memoization arrays. Some recursive problems can also be converted into dynamic programming problems to reduce time complexity further. Finally, such articles summarize recursion’s general characteristics: the code is simple and easy to understand and write. Its drawbacks are high time and space complexity.
That is generally true. Recursive and iterative methods can usually be converted into one another, and iteration is generally more efficient. With careful design, though, recursion can also be highly efficient: examples include merge sort and quicksort. Recursive solutions to many binary tree problems are not only clearer but also more efficient than their iterative counterparts. These include basic traversal and some binary search tree operations. Put another way, this applies to self-referential data structures, such as linked lists, binary tree nodes, and N-ary tree nodes.
The General Form of a Recursive Algorithm
func(){
if some case:
return ;
else{
do something:
func();
}
}
Recursion and Iteration
Recursion repeatedly calls the same function. Intermediate results can be stored in variables that persist through the calls or passed back as return values. Iteration uses loops, with intermediate results stored in already-defined variables. For example, to output the nth term of the Fibonacci sequence:
//基于Java 实现
// 递归
public void int fib(int n){
if( n == 0 || n == 1){
return n;
}
else{
return fib(n - 1) + fib(n - 2);
}
}
//迭代
public void int fib(int n ){
int[] res = new int[n + 1];
res[0] = 0;
res[1] = 1;
for(int i = 2; i <= n; i++){
res[i] = res[i - 2] + res[i - 1];
}
return res[n];
}
// 空间复杂度其实还可以进一步优化为O(1);
Recursion and Binary Trees
Binary tree traversal is particularly straightforward to write recursively.
// 前序遍历
class Solution {
private List<Integer> myList = new LinkedList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return myList;
}
myList.add(root.val);
if(root.left != null) preorderTraversal(root.left);
if(root.right != null) preorderTraversal(root.right);
return myList;
}
}
//中序遍历
class Solution {
private List<Integer> myList = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return myList;
if(root.left != null) inorderTraversal(root.left);
myList.add(root.val);
if(root.right != null) inorderTraversal(root.right);
return myList;
}
}
//后序遍历
class Solution {
List<Integer> myList = new LinkedList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return myList;
if(root.left != null) postorderTraversal(root.left);
if(root.right != null) postorderTraversal(root.right);
myList.add(root.val);
return myList;
}
}
Of course, we can replace recursion with a stack data structure, though the implementation is a little more involved.
// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> st = new Stack<TreeNode>();
List<Integer> myList = new LinkedList<Integer>();
if(root == null) return myList;
st.push(root);
while(!st.empty()){
TreeNode tmpNode = st.pop();
myList.add(tmpNode.val);
if(tmpNode.right!= null){
st.push(tmpNode.right);
}
if(tmpNode.left != null){
st.push(tmpNode.left);
}
}
return myList;
}
//中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if(root == null) return ans;
TreeNode tmp = root;
while(tmp != null || !st.empty()){
while(tmp != null){
st.push(tmp);
tmp = tmp.left;
}
tmp = st.pop();
ans.add(tmp.val);
tmp = tmp.right;
}
return ans;
}
//后续遍历
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
List<Integer> myList = new LinkedList<Integer>();
if(root == null ) return myList;
TreeNode tmpNode = root;
s1.push(root);
while(!s1.empty())
{
tmpNode = s1.pop();
s2.push(tmpNode);
if(tmpNode.left != null) s1.push(tmpNode.left);
if(tmpNode.right != null) s1.push(tmpNode.right);
}
while(!s2.empty())
{
tmpNode = s2.pop();
myList.add(tmpNode.val);
}
return myList;
}
Insertion and deletion in a binary search tree are relatively difficult to implement, but recursion greatly simplifies the implementation without increasing the time complexity compared with other methods.
//insert
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(val < root.val) root.left = insertIntoBST(root.left, val);
else if (val > root.val) root.right = insertIntoBST(root.right, val);
else x.val = val;
return root;
}
}
// delete
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null ) return null;
if(key < root.val) root.left = deleteNode(root.left, key);
else if( key > root.val) root.right = deleteNode(root.right, key);
else{
if(root.right == null) return root.left;
if(root.left == null) return root.right;
TreeNode t = root;
root = min(t.right);
root.right = deleteMin(t.right);
root.left = t.left;
}
return root;
}
private TreeNode min(TreeNode root){
if(root.left == null) return root;
else return min(root.left);
}
private TreeNode deleteMin(TreeNode x){
if(x.left == null ) return x.right;
x.left = deleteMin(x.left);
return x;
}
Checking whether a binary tree is balanced is another example of an elegant recursive algorithm.
public boolean isValidBST(TreeNode root) {
if(root == null ) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean valid(TreeNode root, long min, long max){
if( root == null) return true;
if(root.val <= min || root.val >= max) return false;
return valid(root.left, min, root.val) && valid(root.right, root.val,max);
}
Recursive programs are not necessarily easy to write, nor do they always have high complexity. Used thoughtfully, recursion can balance performance and readability. Of course, when an iterative implementation is already straightforward, there is no need to use recursion.