Recursion is as simple as that.

  algorithm, java, recursive

图片描述

What is recursion?

Wikipedia gives the following definition:

The programming skill of program calling itself is called recursion. Recursion is widely used in programming languages as an algorithm.

The above statement is slightly official. In short, recursion is calling itself, but this call has certain conditions, such as:

  • The subproblem must be the same as the original problem and simpler.
  • The number of calls to itself cannot be too large, otherwise the program stack will overflow.
  • The recursion boundary, that is, the end condition of recursion, must be set, otherwise recursion will loop indefinitely until the program stack overflows.

The difference between recursion and circulation

  • recursive

Advantages: The code is concise and clear (you need to understand the algorithm, otherwise you will feel dizzy)
Disadvantages: The number of calls is not well controlled, which is easy to cause stack overflow. In addition, each pass parameter is equivalent to pushing the stack, and each return result is equivalent to pushing the stack. This process greatly affects the execution efficiency.

  • Cycle

Advantages: simple logic and fast speed
Disadvantages: Not all problems can be solved. Some problems must be implemented recursively. For example, if anyone can write the famous Han-jota problem in other ways, I will take it.

Recursive usage scenarios

With regard to usage scenarios, I have concluded by saying that recursion can be tried when the number of calls is small and the loop implementation is extremely disgusting.

Several Examples of Recursion

  1. Calculates the sum of int arrays
public class Main {

    private static int sum(int[] arr, int z) {

        if (z == arr.length) {
            return 0;
        }

        int x = sum(arr, z + 1);

        int res = arr[z] + x;

        return res;
    }


    public static void main(String[] args) {
        int arr[] = {1, 2};
        sum(arr, 0);
    }
}

This example is the simplest, of course, here is for the convenience of explaining the problem, in fact, it is the best to use circular implementation. The purpose is to calculate the sum of the elements of arr array. Looking at the input parameters, you can guess that the result is 3. Next, I’ll talk about some tips for this kind of program.

First of all, we need to find the recursive boundary of the program, that is, the condition for recursion to end (this is not accurate either, depending on the specific code implementation, sometimes the recursive boundary is indeed the condition for recursion to end, returning the final result, but sometimes it is also the condition for the last layer of recursion to return the result, such as the following program).

  • When z = 2, this layer of recursion returns 0, that is, x = 0 and z = 1.
  • At this time, res = arr[1]+0 returns res = 2, that is, x = 2 gives this layer of recursion to z = 0.
  • At this point, res = arr[0]+2 = 3, the recursion ends and the result is returned to the caller.

If you don’t understand, please copy the code debug and run it step by step. At first, I was dizzy anyway.

  1. Calculate the sum of 1 to 100
public class Main {

    static int i = 1;

    public static void show(int sum) {
        sum = sum + i; //业务代码1
        //递归头
        if (i == 10) {
            System.out.println(sum);
            return;
        }
        i++;   //业务代码2
        show(sum); //递归体
    }

    public static void main(String[] args) {
        int sum = 0;
        show(sum);
    }
}

The recursion boundary written above belongs to what I said above. It is the condition for recursion to end. Its return result is the final result of recursion, not the result of the previous level.

  1. Fibonacci sequence
public class Main {
 
    public static int f(int n) throws Exception {
        if(n==0){
           throw new Exception("参数错误!");
        }
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return f(n-1)+f(n-2); //自己调用自己
        }
 }
 
 
    public static void main(String[] args) throws Exception {
        for (int i = 1; i <=10; i++) {
            System.out.print(f(i)+" ");
        }
    }  
}
  1. Calculate folder size

Since the length () (return value type is long) method under the File class can only count the file size, there is no method to directly count the folder size, so it is necessary to use recursive method to traverse all files and accumulate them to finally calculate the folder size.

public class Main {

    public static void main(String[] args) {
        File dir = getDir();
        System.out.println(getFileLength(dir));
        System.out.println("统计完成!");
    }
    
    public static File getDir() {
        //1,创建键盘录入对象
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个文件夹路径:");
        //2,定义一个无限循环
        while(true) {
            //3,将键盘录入的结果存储并封装成File对象
            String line = sc.nextLine();
            File dir = new File(line);
            //4,对File对象判断
            if(!dir.exists()) {
                System.out.println("您录入的文件夹路径不存在,请重新录入:");
            }else if(dir.isFile()) {
                System.out.println("您录入的是文件路径,请重新录入:");
            }else {
                //5,将文件夹路径对象返回
                return dir;
            }
        }        
    }

    public static long getFileLength(File dir) {
        //1,定义一个求和变量
        long len = 0;
        //2,获取该文件夹下所有的文件和文件夹listFiles();
        File[] subFiles = dir.listFiles();
        //3,遍历数组
        if(subFiles != null) {
            for (File subFile : subFiles) {
                //4,判断是文件就计算大小并累加
                if(subFile.isFile()) {
                    len = len + subFile.length();
                    //5,判断是文件夹,递归调用
                }else {
                    len = len + getFileLength(subFile);
                }
            }
        }
        return len;
    }
}

Summary: This article mainly introduces the definition of recursion, the difference between recursion and loops, and its use scenarios. Finally, it provides several code examples for everyone to study. If you don’t understand it, please copy the code and debug it step by step.

Reference link:https://www.jianshu.com/p/edfc4e35f383

Recommended reading:

1. java | What is Dynamic Proxy

2. SpringBoot | Startup Principle

3. SpringBoot | Automatic Configuration Principle

一个优秀的废人