Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

A recursive

1.1 Basic concepts of recursion

Recursion is a method of solving a problem by continually breaking it into smaller sub-problems and solving it by dealing with ordinary sub-problems. Recursive functions are functions that call themselves directly or indirectly through a series of statements. Note that each time a recursive function calls itself, it simplifies the original problem, and eventually the sequence of smaller problems must converge to the base case, solving the problem and terminating the recursion. Recursion is a very elegant way to solve complex problems. Many mathematical functions are defined recursively, such as factorial functions defined recursively:


n ! = { 1 . n = 0 n ( n – 1 ) ! . n > 1 n! = \begin{cases} 1, & {n=0} \\ n(n-1)! , & {n>1} \end{cases}

Although this definition is recursive, it is not an infinite loop that cannot be terminated. In fact, it’s very easy to compute factorials using this function. For example, calculate 3! 3! 3! By definition, we have 3 factorial. = 3 (3, 1)! = 3 (2! 3! = 3 (3, 1)! = 3 (2! 3! = 3 (3, 1)! = 3 (2! And then we need to solve for 2! 2! 2! , again apply definition 3! = 4 (2! = 3 [(2) (2-1)!] = 3 (2) (1!) Continue this process, and finally we need to compute 0! 0! 0! And by definition 0! = 10! = 10! =1, the calculation process ends: 3! = 3 (2! = 3 (2) (1!) = 3 (2) (1) (0!) = 3 (2) (1) (1) = 63! = 3 (2! = 3 (2) (1!) = 3 (2) (1) (0!) = 3 (2) (1) (1) = 63! = 3 (2! = 3 (2) (1!) = 3 (2) (1) (0!) = 3 (2) (1) (1) = 6

As you can see, the recursive definition is not an infinite loop, because each time the definition is applied, the program breaks down the problem into simpler subproblems, in the factorial function example, that is, calculating the factorial of smaller numbers up to 0! 0! 0! And you don’t have to apply recursion again. When the recursion ends, we get a closed expression that can be evaluated directly, also known as the “base case” of recursion. When a function calls itself to perform a subtask, it is called a “recursive case.”

1.2 The importance of recursion

Recursive function is an important programming technique borrowed from mathematics. Usually, recursion can greatly reduce the amount of code, which is very useful in many tasks that can be decomposed into subproblems. For example, sorting, traversing and searching can be quickly solved by recursive methods.

1.3 Three principles of recursion

Like many algorithms, recursion has important principles to follow, called the three principles of recursion:

  • Recursive algorithms must have a base case;
  • Recursive algorithms must change state and gradually converge to the base case;
  • A recursive algorithm must contain recursive cases that recursively call itself.

It is important to note that the core idea of recursion is not looping, but breaking problems into smaller, easier to solve subproblems.

1.4 Application of recursion

Recursion plays a very important role in programming. Here are some practical scenarios in which recursion is commonly used:

  • Fibonacci series, factorial calculation and other mathematical problems;
  • Merge sort, quicksort;
  • Binary search;
  • Tree and graph traversal and related problems;
  • Hanoi.

2 recursion examples

In this section, we will start with a simple list sum problem to see how recursive algorithms can be used.

The list of sum

List summation is a very simple problem, and it’s perfect for understanding the idea of recursive algorithms. For example, if we need to calculate the sum of the list [1, 2, 3, 4, 5], we can write the following code to calculate the sum of all the numbers in the list if we use a loop function:

def sum_list(list_data) :
    result = 0
    for i in range(list_data):
        result += i
    return result
Copy the code

How do we solve this problem if we don’t use loops? We can write summation process ((((1 + 2) + 3) + 4) + 5) ((((1 + 2) + 3) + 4) + 5) ((((1 + 2) + 3) + 4) + 5), and according to the commutative law of addition, Calculation process can be written as (1 + (2 + (3 + 4 + 5 ()))) (1 + (2 + (3 + 4 + 5 ()))) (1 + (2 + (3 + 4 + 5 ()))), then we can clearly see that the list of data list sum equal to the first element and the rest of the elements:


s u m _ l i s t ( l i s t _ d a t a ) = l i s t _ d a t a [ 0 ] + s u m _ l i s t ( l i s t _ d a t a [ 1 : ] ) sum\_list(list\_data)=list\_data[0]+sum\_list(list\_data[1:])

Use Python to implement the above equation as follows:

def sum_list(list_data) :
    if len(num_list) == 1:
        return list_data[0]
    else:
        return list_data[0] + sum_list(list_data[1:)Copy the code

In the code, the function exit condition is first given, which is the basic case of a recursive function, in this case a list of length 1 whose elements sum is the number in the list. If the exit condition is not met, sum_list calls itself, which is how recursive a recursive function is, and why it is called a recursive function.

In figure (a) below, you can see the recursive call process for solving [1, 2, 3, 4, 5]. Each recursive call is solving a problem closer to the base case until the problem cannot be further simplified.

When the problem cannot be simplified, we begin to concatenate the solutions of all the subproblems. Figure (b) below shows the addition operation performed by the recursive function sum_list when it returns the results of a series of calls. When it returns to the top level, the original problem is solved.