Recursion & iteration

recursion

Recursion is often used to describe the process of repeating things by self similar method. In mathematics and computer science, it refers to the method of using function itself in function definition. (A calls A)

iteration

Repeat the activity of the feedback process, and the result of each iteration will be used as the initial value of the next iteration. (A repeatedly calls B)

Such as title

There are n steps. You can only take one or two steps at a time. How many walking methods are there?

Recursive thinking

• N = 1 - > next step - > F (1) = 1
• N = 2 - > (1) step by step (2) directly take 2 steps - > F (2) = 2
• N = 3 - > (1) first reach the first step (f(1)), and then directly take two steps
  (2) First reach the second step (f(2)) - > F (3) = f (1) + f(2)
• N = 4 - > (1) first arrive at f(2), and then directly take two steps
  (2) First reach the second step f(3), and then directly take one step - > F (4) = f (2) + f(3)
• ···
• n=x (1) arrive at f(x-2) first, and then take two steps directly
  (2) First reach the second step f(x-1), and then directly take one step - > F (x) = f (X-2) + f(x-1)

Loop iteration idea

• N = 1 - > next step - > F (1) = 1
• N = 2 - > (1) step by step (2) directly take 2 steps - > F (2) = 2
• N = 3 - > (1) first reach the first step (f(1)), and then directly take two steps
  (2) First reach the second step (f(2)) - > F (3) = f (1) + f(2)
• N = 4 - > (1) first arrive at f(2), and then directly take two steps
  (2) First reach the second step f(3), and then directly take one step - > F (4) = f (2) + f(3)
• ···
• n=x (1) arrive at f(x-2) first, and then take two steps directly
  (2) First reach the second step f(x-1), and then directly take one step - > F (x) = f (X-2) + f(x-1)

It can be seen from the above that no matter how many steps there are, we have to go to the last n-1 or n-2 steps, so we can save these two situations with two temporary variables one = (f(n)-1) and two = (f(n)-2)!

Test site of this question

• recursion
• Cyclic iteration

Problem solution

Recursive mode

public class Recursion {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(f(42));
        long end = System.currentTimeMillis();
        System.out.printf("The time-consuming milliseconds are:%d", end - start);
    }

    /**
     * There are n steps, only one or two steps at a time. How many kinds of recursive code implementations are there
     * The performance loss is serious, especially when the amount of data is large, it may cause stack overflow
     *
     * @param n Value to be calculated
     * @return Calculation results
     */
    public static int f(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return f(n - 2) + f(n - 1);
    }
}

Cyclic iteration

public class LoopIteration {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(loopIteration(42));
        long end = System.currentTimeMillis();
        System.out.printf("The time-consuming milliseconds are:%d", end - start);
    }

    /**
     * Circular iteration solves the problem of how many walking methods there are with n steps and only one or two steps at a time
     *
     * @param n Value to be calculated (number of steps)
     * @return Results (how many walking methods)
     */
    public static int loopIteration(int n) {
        if (n < 1) {
            throw new IllegalArgumentException(n + "Cannot be less than 1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        // When n=3, one=f(3-1)=f(2)=2,two=f(3-2)=f(1)=1
        int one = 2; // Initialization needs to go one step at the end
        int two = 1; // Initialization takes two steps to the end
        // Total steps
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = one + two;
            // When i=4, two=f(4-2)=f(2)=2, so it's the last one
            two = one;
            // When i=4, one=f(4-1)=f(3)=3, so it is the last sum
            one = sum;
        }
        return sum;
    }
  }

Summary

• Comparing the execution time of the above two methods, we can see that recursion consumes more time, so never use recursion where iteration can be used
• Both methods simplify the big problem into a small problem, and deduce the final result step by step from the small problem
• Theoretically, all recursion and iteration can be converted to each other, but in fact, from the perspective of algorithm structure, the structure of recursive declaration can not always be converted to iterative structure (the reason needs to be studied)
• The method call itself is called recursion, and the new value derived from the original value of the variable is called iteration
• recursion
  • Advantages: large problems are transformed into small problems, which can reduce the amount of code, simplify the code and have good readability
  • Disadvantages: recursive call wastes space, and too deep recursion is easy to cause stack overflow
• iteration
  • Advantages: the code runs efficiently, because the time increases only with the increase of the number of cycles, and there is no additional space overhead
  • Disadvantages: the code is not as concise as recursion, and the readability is not very good (not easy to understand)