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:

** Stop function **: Part of own function
** 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:

Determine the problem to be solved with a recursive function.

Consider one-step simple problem from problem to solve .

One-step simple problem 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 (I believe with all my heart). Let the solution be sol1.

Use sol1 to express the solution (let's call it sol) of the problem to be solved .

Assuming that problem to be solved is a problem related to n problems, one-step simple problem 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.

Create recursive function name
Convert stop functions to code
Convert recursive features into code
Determine the problem to be solved with a recursive function.

Consider one-step simple problem from problem to solve .

One-step simple problem can be solved by the function that I will make ** I believe with all my heart **! Let's name the function fun.

You can solve one-step simple problem from fun. Let the solution be sol1.

Use sol1 to express the solution (let's call it sol) of the problem to be solved .

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.)

Let the recursive function name be reverse_string:
```
def reverse_string(str1):
```

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

Convert recursive features into code
Problem to solve : Invert the string str1

One-step simple problem : 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:]
```

One-step simple problem can be solved by your own function (reverse_string) ** I believe with all my heart **!

The solution obtained by the reverse_string function for the one-step simple problem 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)
```

From sol1, express the solution (sol) of problem to be solved . 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.