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
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
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
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).
factional (1) returns
1 * factional (0).
factional (0) will return
1 depending on the condition of the
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.