[PYTHON] How to make a recursive function

Difficult to make a recursive function

It's difficult to create a recursive function, isn't it? There are many commentary articles on recursive functions, but it seems that there are few articles that explain how to create recursive functions, only explaining the code of recursive functions that already exist. ..

If you investigate the article on how to make a recursive function, English article here shows the flow of making a recursive function. I explained it in an easy-to-understand manner. I tried to translate the content of the English article by myself, so I would like to share it.

1. What is a recursive function?

In a nutshell, a function whose function contains its own call. For details, please refer to other articles.

2. Two functions that make up a recursive function

First, let's understand the functions that make up a recursive function. Two functions are needed to construct a recursive function:

  1. ** Stop function **: Part of own function
  2. ** Recursive function **: The part where the function calls itself

For example, consider a recursive function that inverts a string. Let's divide it into the above two functions:

def reverse_string(str1):
    #Stop function
    if len(str1)<2:
        return str1

    #Recursive function
    return reverse_string(str1[1:])+str1[0]

I think it's relatively easy to convert the part of the stop function into code. On the other hand, ** it can be difficult to convert recursive features into code **. Therefore, I will explain the flow of converting this recursive function into code.

3. Flow of converting recursive functions into code

Convert recursive functionality into code with the following flow:

  1. Determine the problem to be solved </ font> with a recursive function.
  2. Consider one-step simple problem </ font> from problem to solve </ font>.
  3. One-step simple problem </ font> can be solved by the function that I will make ** I believe with all my heart **! From 4.3, you can solve one-step simple problem </ font> (I believe with all my heart). Let the solution be sol1.
  4. Use sol1 to express the solution (let's call it sol) of the problem to be solved </ font>.

Assuming that problem to be solved </ font> is a problem related to n problems, one-step simple problem </ font> is an image of a problem related to n-1 problems. .. The meaning of the explanation in the preamble will be concretely shown in the example in Chapter 5.

4. Flow to create recursive function

In Chapter 3, we created a flow that converts recursive functions into code. Now, let's summarize the flows that make up the recursive function.

  1. Create recursive function name
  2. Convert stop functions to code
  3. Convert recursive features into code
  4. Determine the problem to be solved </ font> with a recursive function.
  5. Consider one-step simple problem </ font> from problem to solve </ font>.
  6. One-step simple problem </ font> can be solved by the function that I will make ** I believe with all my heart **! Let's name the function fun.
  7. You can solve one-step simple problem </ font> from fun. Let the solution be sol1.
  8. Use sol1 to express the solution (let's call it sol) of the problem to be solved </ font>.

5. Example

Let's create a recursive function that solves the following example according to the flow in Chapter 3.

** Problem: Invert the string. (Ex: abc → cba) **

Let str1 be the character string you want to invert. (Coded in Python.)

  1. Let the recursive function name be reverse_string:

    def reverse_string(str1):
    
  2. Convert stop function to code:

    def reverse_string(str1):
        #Stop function
        #If the length of the character string is 1, it comes out of the function.
        if len(str1)<2:
            return str1
    
  3. Convert recursive features into code

  4. Problem to solve </ font>: Invert the string str1

  5. One-step simple problem </ font>: Invert "character string with the first character deleted from the character string string" (this is called str1_rem). Here, let's express str1_rem in code:

    ```python
    def reverse_string(str1):
        #Stop function
        #If the length of the character string is 1, it comes out of the function.
        if len(str1)<2:
            return str1
    
        #Delete the first character from the string str1
        str1_rem=str1[1:]
    ```
    
  6. One-step simple problem </ font> can be solved by your own function (reverse_string) ** I believe with all my heart **!

  7. The solution obtained by the reverse_string function for the one-step simple problem </ font> is sol1 (I believe with all my heart). That is, sol1 = reverse_string ("a string obtained by subtracting the first character from the string string") (I believe with all my heart):

    ```python
    def reverse_string(str1):
        #Stop function
        #If the length of the character string is 1, it comes out of the function.
        if len(str1)<2:
            return str1
    
        #Delete the first character from the string str1
        str1_rem=str1[1:]
    
        #reverse_string is str1_I believe with all my heart that I can reverse before.
        sol1=reverse_string(str1_rem)
    ```
    
  8. From sol1, express the solution (sol) of problem to be solved </ font>. If "the first character of the character string string" is added after sol1, it becomes sol. Mathematically speaking, sol = sol1 + "the first character of the string string":

    ```python
    def reverse_string(str1):
        #Stop function
        #If the length of the character string is 1, it comes out of the function.
        if len(str1)<2:
            return str1
    
        #Delete the first character from the string str1
        str1_rem=str1[1:]
    
        #sol1 is str1_I believe with all my heart that it is a character string that is the reverse of before.
        sol1=reverse_string(str1_rem)
    
        #Express sol from sol1
        sol=sol1+str1[0]
        
        return sol
    ```
    

** Curiously, this creates a recursive function **! ..

If you shorten the above code,

def reverse_string(str1):
    if len(str1)<2:
        return str1
    return reverse_string(str1[1:])+str1[0]

It becomes.

6. Impressions

If the Japanese article is difficult to understand, the details are often written in the English article. Before you get used to it, it is recommended to write the above flow before coding. At first, let's practice with a simple example. For example, the problem of displaying all the elements of an array.

Acknowledgments

We would like to thank those who commented and those who corrected it.

Recommended Posts