A recursive function is a function that calls itself within the function. For example, the following code is a recursive function.

```
def hello
puts 'hello!'
hello
end
hello
```

In the function called hello, the hello function is called again after outputting the string `hello!`

.
By the way, when I execute the above code, the string `hello!`

Is output all the time. (If it is ruby, it will be forcibly terminated with "System Stack Error")

If you just create a recursive function, the above code will achieve your goal, but since a recursive function that outputs a character string is not interesting, let's take up "factorial calculation" as a basic problem of implementing a recursive function. I wrote the code to calculate the factorial of n. First, let's implement it without using a recursive function.

```
res = 1
while n > 0
res *= n
n -= 1
end
puts res
```

Is it like this?
Also, ruby has a convenient method called `times`

method, so if you use it, it will be as follows.

```
res = 1
n.times do |i|
res *= (i + 1)
end
puts res
```

In both cases, the factorial can be calculated by passing a natural number to `n`

.
Let's implement this with a recursive function. The code looks like this:

```
def factorial(n)
if n == 0
1
else
n * factorial(n - 1)
end
end
```

If you pass a natural number to the `factorial`

function, the program will return the result of the factorial.
If you are not accustomed to it, it is difficult to understand the flow of processing at first glance, so let's follow the processing using the case of `n = 3`

as an example.

If you pass `n = 3`

as an argument to` factional`

, the `if-else`

block evaluates` n`

and branches. Since `n = 3`

, the processing of` else`

runs and `3 * factional (2)`

is returned.
However, since we are calling the `factional`

function on the return value, the process runs here as well and the result is returned. `factional (2)`

returns `2 * factional (1)`

.
Similarly, `factional (1)`

returns`1 * factional (0)`

.
Here `factional (0)`

will return `1`

depending on the condition of the` if-else`

block.
As a result, `factional (3)`

will return` 3 * 2 * 1 * 1`

, and you will get the answer you want, `3! = 6`

.

When creating a recursive function, ** a condition to end the process ** is required. Such a condition is called a ** base case **. If the base case is not set, the recursive function will end up in an infinite loop. A base case is essential to avoid infinite loops. In this factorial calculation code, the case of "n = 0" is the base case. It is also important to build a process that will allow you to reach the ** base case. ** Even if you prepare a base case, if you do not reach the base case, the process will not end. For example, the following code will result in an infinite loop.

```
def factorial(n)
if n == 0.5
1
else
n * factorial(n - 1)
end
end
```

The condition of `if`

is a decimal point. Since n is a natural number, there is no case where n is a decimal. In such an example, the base case cannot be reached.

Being able to write loop processing with recursive functions expands the range of programming. The idea of recursive functions is also important (apparently, still studying) when implementing algorithms such as depth-first search. In a simple example like this factorial calculation, it seems easier to understand if it is implemented in a normal loop, but when implementing an algorithm such as depth-first search, it is simple to use a recursive function. I think it can be implemented with simple code.

qiita: What kind of world will expand when you learn recursive functions

Recommended Posts