Algorithms – How to understand recursion and write a recursive function

Not naturally every programmer to understand recursion, just in the freshman year, when the other people to write the first and greatest common divisor of recursive functions, for its amazing how, can need not circulation, unexpectedly code can be so simple, indeed, in most cases, recursive implementation code is very short, and when most people know that recursion, also can understand basic recursion, But often do not know how to write, or write recursion is often dead cycle, write algorithm is often learned is routine, only a few people are to create an algorithm, most people are to use the algorithm, and recursion is really a routine to follow.

This article is from the recursive zama step, from a few simple examples to the general set, step by step to break down the recursion

Three elements of recursion

When you write recursion, you write the implementation of the three elements, the function, the boundary, and the recursive formula, and you just remember to write it this way, and after you write a few algorithms, you’ll see why you do it this way.

1.1 Recursive primary element – function

Define what your function does, what its input arguments should be, what its return value should be, and start with what the function does. You can define a function f(), assuming that you have implemented each step of the recursion, and then define what the implementation actually does, what the input arguments should be at least, Return value and parameter return can be understood as the same thing, both to return to the upper call or global a data, think about the three elements of a function, then your function is defined.

1.2 Recursive boundary, jump out of recursion

Also, the first to do this, why to want to, this step is to determine the is function into the participation, the participation of null, the parameter as the initial value, such as the Fibonacci sequence of one or two before the start time may not necessarily want completely, it doesn’t matter, the following step will also continue to improve, so I have to example here is Fibonacci top 1 or 2, Instead of saying the conclusion, this step is in the implementation of the function, so the way to think about it is assuming that the entry is at a critical value or an initial value or a special value, and you have to decide, the first time you write it like Fibonacci, you can just write it this way

if (n == 1)
  return 1;
if (n == 2)
  return 1; 
Copy the code

It doesn’t have to be exactly right, it doesn’t have to be that elegant, just think about boundaries. Now what does the boundary mean? There are two things, first, outliers boundary, and the other end of the recursive judgment, such as this topic of n < 0 to do, and n = = 1 and n = = 2 respectively corresponding to said earlier, both may consider not so completely, of course, if you only consider the like in the previous code, or write border to find more, or redundancy, That doesn’t affect the result of the program, so after we write the recursion formula, we’ll review the boundary problem.

1.3 Recursive formula

This is going to start with meaning, and then implementation, and meaning is to gradually reduce the size of the algorithm, or to define a way to get the input value as close to the critical value as possible, which is to find a relationship between f(n) and f(n-x) sequence, where F (n) is the size of the problem to be solved, and f(n-x) is the function of the size of the problem that f(n-x) is smaller than n, This is the key step in recursive functions, no recursive formula, no recursion. For example, the Fibonacci sequence, the recursion formula is f(n)=f(n-1) + f(n-2). If we look at this formula, we find that the NTH is related to n-1 and n-2. So let’s see, if we input any integers, then n-1,n-2 could be negative, 0,1 +, It can be seen that the boundary 0 and negative numbers are not taken into account. Therefore, recalling the previous 1.2 recursion, we can supplement the boundary to obtain:

if (n <= 2)
  return 1;

Copy the code

Case of recursion

Here are three simple examples to practice using recursion, namely frog jump step problem, equivalent to Fibonacci sequence, recursively reverse single linked list, recursively traverse tree, and for three

2.1 Frog jumping on steps

First define functions, clear function is only a single input values of n, the second end find recursive or recursive boundary conditions, can be found when the steps is the most easy to get 1 or 2, as to the recursive formula, can be found that frog jump at every time when there are two method, the frog how to get to the NTH step, is to have two kinds of jump method, Corresponding to f(n-1) and F (n-2) respectively, so the recursion is F (n)= F (n-1)+f(n-2), so the whole algorithm is as follows:

// A frog can jump up one step or two at a time. Find out how many ways the frog can jump up n steps.
/ / 1. Define a function
public int f2(int n) {
   //2. Define boundaries
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
   //3. Determine the recursion
    return f2(n-1) + f2(n-2);
}
Copy the code

If n is less than 1, it will go into an infinite loop.

if (n == 1)
  return 1;

if (n == 2)
  return 2;

if (n < 1)
  return 0;
  
// You can write it like this

if (n < 1)
  return 0;
if (n <= 2)
  return n; 
Copy the code

2.2 Recursively reverse a single linked list

Similarly, first define the function and find that the function has only one input parameter, namely node node, which is applicable to the root node or any intermediate node. Second determine the boundary. When reversing the single linked list, it may miss the boundary of Node.next. There are two ways to do this: (1) redundant writing, as long as you consider that this is probably the boundary, you can never go wrong with writing too much, and you can even write two or three more steps and still be fine. (2) Less writing, you can write recursively and then check, for example, reversing a single linked list. You’ll see that if Node.next is empty, Node.next-next will report a null pointer problem. After writing a recursion, it is best to go back and check the boundary.

The heart of the problem is the recurrence for untying the chain, which is

Node last = f3(node.next); // Assume that the list after the next node of the current node has been reversed
node.next.next = node; // The node that the current node points to points to the current node
node.next = null ;// The current node points to the next node
// If the first node is reversed and the last node is reversed, then the pointer is null. Otherwise, it still points to 2
// What if it is not the first node? How does this pointer point to
Copy the code

For example, if a singly linked list is 1,2,3,4,5, the recursion will look like this:

If the current node in each step is the last one in the inversion list, it must point to null.

class Node{
    int data;
    Node next;
} 
public Node f3(Node node) {
    //2. Determine the return boundary
    if (node == null || node.next == null)
        return node;
    //3. Get the recursion
    Node last = f3(node.next);
    node.next.next = node;
    node.next = null ;// What does this do? And then you end up with A->B,B->A
    return last;
}
    
Copy the code

2.3 Recursively traversing the tree

Recursively traversing a tree is also the easiest. Assuming you haven’t seen the traversal code before, start from zero. Define the function first, confirm that the input parameter is similar to the single-linked list inversion, requiring only one TreeNode node, and then consider null and non-NULL boundaries.

if (node == null)
  return ;

if (node.left == null && node.right == null) {
  System.out.pritln(node.val);
  return ;
}

Copy the code

Now it seems a little redundant, but assuming you don’t know, let’s do the next recursion, using preordering as an example

// Start with the node itself
System.out.println(node.val);      
// Then the node is left
preOrder(node.left);      
// Then the node is right
preOrder(node.right); 
Copy the code

If the node is null, we return the byte boundary from the parent node. If the node is null, we return the byte boundary from the parent node. If the node is null, we return the byte boundary. So the final pre-middle/post-middle traversal is as follows:

 // binary tree forward traversal
public static void preOrder(TreeNode node) {
    if (node == null)
        return;
    System.out.println(node.val);
    preOrder(node.left);
    preOrder(node.right);
}

// Order traversal in binary tree
public static void inOrder(TreeNode node) {
    if (node == null)
        return;
    preOrder(node.left);
    System.out.println(node.val);
    preOrder(node.right);
}

// binary tree traversal
public static void postOrder(TreeNode node) {
    if (node == null)
        return;
    preOrder(node.left);
    preOrder(node.right);
    System.out.println(node.val);
}
Copy the code

2.4 Construct a binary tree from a sequence

Below, we fill a recursive algorithm, input a binary tree sequence, to restore the construction of binary tree, by the way test the previous traversal tree code, also familiar with the recursive routine, we directly to write code

//1. Define function validation, only need one argument, that is, the remaining sequence
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        // Define an empty tree node, which can be used in both bounds and recursion bodies for uniformity, so write it in the first line
        TreeNode node = null;
        / / 2. The boundaries
        if (inputList == null || inputList.isEmpty())
            return node;

        //3. Main recursion body, delete from the list and take the first element, build the left and right nodes, and return the current node
        Integer data = inputList.removeFirst();
        // the list is null. // The list is null
        if(data ! =null) {
            node = new TreeNode(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;
}

    public static void main(String[] args) {
        // preorder traversal sequence
        LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3.2.9.null.null.10.null.null.8.null.4}));

        TreeNode node = createBinaryTree(inputList);

        // preorder traversal
        System.out.println("Sequential traversal:");
        preOrder(node);

    } 
Copy the code

3. Summary

To write a good recursion, there are three steps: first, determine the input value of the function, the return value, that is, what the function itself does. Second, judge the boundaries. Write down all the boundaries you can think of. Finally, write the recursive body, including the return value of the function, and then go back and check the boundaries, adding, deleting, changing and checking the boundaries.

Ps: more cases, just do not want to good algorithm is how, if you want to good, can use the simulation method, the whole picture out, write code reference this article, can be done in one go…