Questions about recursive functions (Tower of Hanoi, etc.)

Is the question a concern about how to determine whether the problem can be implemented as a recursive function or not?

If the steps are clearly defined or the logic (logic) is clear, it is easy to derive that the recursive function can be easily implemented (many problems can be sufficiently implemented with repetitive statements that do not use recursive).)

However, this seems to have been possible because the steps are clearly presented, and if you consider the direct algorithm, it will be difficult to define the steps clearly unless you follow logic.

The expression on the right was easily derived because, as you said, the instructor did not "directly derive the logic without looking back" but understood the logic and defined the steps clearly. In addition, it is recommended that you have an understanding of basic logic and use tools (coding) because unexpected problems can occur when using it in practice.

Thank you.

The way to implement a recursive function is to find the same problem that resembles the current problem in the process of solving the problem without first thinking about implementing it. And you have to have the answer to the simplest problem. The trick is to assume that the problem has already been resolved.

This approach is usually called mathematical induction Mathematical induction consists of the following processes:

A recursive function, so to speak, is a function that implements 3 through 1 and 2.

For example, n Factory (1*2*3*... * Let's say we write a recursive function to get n).

n Factory definition is 1 * 2 * 3 *... * It's n.

This is (1 * 2 * ... * n - 1) * n, (n-1 Factory) * n.

In the process of obtaining the solution, we found the same part of the problem.

And the simplest problem, the value of 1 factory is 1.

If the function is f, you can write:

f(n):
  if (n == 1) return 1
  return f(n-1) * n

Let's move on to the Hanoi Tower.

The Hanoi Tower is the problem of moving the stacked discs to another pillar.

There are three columns, a, b, and c, and for convenience, I will mark the original plate in an array as below.

[1, 2, 3, 4], [], [] Take an example of a disk of sizes 1, 2, 3, and 4 in the first column.

We assume that we already know how to move n Hanoi towers from a to c. That's f(n, a, b, c).

Now, if we put [1, 2, 3], [] and [], we can move to Column b and Column C, right? That is,

[1, 2, 3, 4], [], [] -> [4] [1, 2, 3] [] : f(3, a, c, b)

[1, 2, 3, 4], [], [] -> [4] [] [1, 2, 3] : f(3, a, b, c)

But you can't move to c. C has to have four.

So you have to move [1, 2, 3] to column b first and then move 4 to column c.

[4] [1, 2, 3] [] -> [] [1, 2, 3] [4]: 1 (This value is equal to f(1, a, b, c))

[] [1, 2, 3] [4] -> [] [] [1,2,3,4] : 1 + f(3, b, a, c)

That is, f(4, a, b, c) = f(3, a, c, b) + 1 + f(3, b, a, c).

This is how we found the part that you question.

In the example above, 4 is used as an example, but if you express it as n,

f(n, a, b, c) = f(n-1, a, c, b) + 1 + f(n-1, b, a, c).

So let's find the underlying conditions. f(1, a, b, c) = 1. (Obvious?) Now, if you write it in code, it's like this.

f(n, a, b, c):
  if (n == 1) return 1
  return (
    f(n-1, a, c ,b) +
    1 +
    f(n-1, b, a, c)
  )

A recursive function can be made into a function after understanding the recursive nature of the action you want to do. Most common functions analyze the flow of code by following it from top to bottom and from left to right. The only recursive function doesn't have to follow the flow, and the deeper the step, the less you understand it.

Recursive functions are mainly used for things that do recursive behavior, for example, Fibonacci sequences, factories, Hanoi towers, tree tours, etc.

Usually, even people who think I'm a little salty sometimes don't understand recursive functions well at first, but I think it's because I'm trying to understand them with existing coding stereotypes.

As you asked, we derive an expression and we construct a function accordingly, and if the function works well in some tests, you don't have to think about the flow. It is good to review the flow at least once in the first learning stage, but you never need to review it more than twice.

A recursive function is a recursive function if you write yourself within a function, but two conditions are required to become a practical recursive function. One is that you need escape conditions that allow you to escape from a recursive functions. Second, when calling yourself again inside a recursive function, the argument must be different from the function's parameters. Only then can escape conditions be established someday. These are the features of the recursive functions that you can use, and any recursive function will satisfy everyone.

Until the recursive function is understood, you might think, "Is this distant?" But once you understand it, you'll feel at ease like, "It's nothing."

Don't follow the flow of code too much, throw away the stereotype, set up the expression first as explained in the Internet article or book, and make it into the code. If you can make a recursive expression, you can make it into a code as it is, which is also an advantage of a recursive function.

Recursive functions can be used to speed up the program. Misuse can also slow you down. Also, there are things like Hanoi Tower and Tree Tour that you can never solve without knowing the recursive function, so it's good to get used to.