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

Recommended Posts

Introduction to Recursive Functions: What is a Recursive Function?
Introduction to Ratpack (1) --What is Ratpack?
What is a constructor?
What is a stream
What is a Servlet?
What is a wrapper class?
What is a boolean type?
What is a Ruby module?
What is a floating point?
What is a meaningful comment?
What is a jar file?
What is a Java collection?
What is a lambda expression?
What is a fa⁉ enum?
Function is very easy to use
What is a snippet in programming?
What is a column Boolean type?
What is a reference type variable?
What is a lambda expression (Java)
[Swift] What is "inheriting a class"?
What is a Ruby 2D array?
A good way to make a recursive function that reverses the characters
What is a class in Java language (3 /?)
What is a terminal? -Absolute path & relative path-
What is a Spring Boot .original file?
[For programming beginners] What is a method?
What to do when a javax.el.PropertyNotWritableException occurs
[Introduction to Java] How to write a Java program
What is a class in Java language (1 /?)
What is a class in Java language (2 /?)
JVM Performance Tuning: What is Tuning and How to Make a Good Plan
[Rails] What is a dot (.) Or a colon (:)?
[Introduction to JSP + Servlet] A little animation ♬
What is Docker? I tried to summarize
What is a request scope? Image commentary
What to do if you get a SQLite3 :: BusyException: database is locked error
What to do when you want to delete a migration file that is "NO FILE"
Androd: What to do about "The Realm is already in a write transaction in"
What to do when is invalid because it does not start with a'-'
Add a tag function to Rails. Use acts-as-taggable-on
[Android] Implement a function to display passwords quickly
What a beginner did to understand Object Orientation
How to make a follow function in Rails
[Introduction to Spring Boot] Authentication function with Spring Security
What is Cubby
What is Docker?
What is java
What is Keycloak
What is maven?
What is Jackson?
Introduction to SWING
What is Docker
What is self
What is Jenkins
What is ArgumentMatcher?
What is IM-Juggling?
What is params
What is SLF4J?
Introduction to web3j
What is Facade? ??
What is Java <>?