Introduction to Recursive Functions: What is a Recursive Function?

Let's create a recursive function

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

Recursive function points

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.

Why learn recursive functions

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.

reference

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