Recursion and dynamic programming are two processes that are just the opposite but have the same idea of solving a problem. Both two methods work by taking a significant problem and making it small enough to solve in one step. So in today’s article from AlgoMonster on USATechnews.com, we will continue to look deeper into recursion and dynamic programming.
What is Recursion?
Let’s start with a definition: a recursive algorithm is an algorithm that calls its functions or methods directly or indirectly.
The essence of a recursive algorithm is to decompose a problem into smaller subproblems of the same kind and then recursively call methods to represent the solution to the problem. It has the following characteristics:
1. the solution of a problem can be decomposed into several subproblems.
2. the problem and the decomposed subproblems are identical except for the difference in data size.
3. there is a recursive termination condition, i.e., there must be an explicit recursive end condition, called recursive exit.
The further explanation of Recursion
First, the solution of a problem can be decomposed into several subproblems.
A subproblem is a problem with a smaller data size compared to its predecessors.
In the dynamic diagram, problem ① (a large area) is divided into problem ②, and problem ② consists of two subproblems (two medium regions).
Second, this problem and the decomposed subproblem are identical except for the difference in data size.
The logic of “dividing ① into ②” and “dividing ② into ③” is the same, and the solution idea is the same.
Third, there is a recursive termination condition, i.e., there is a recursive exit.
The problem is decomposed into subproblems, and then subproblems are decomposed into subproblems, layer by layer.
The division of ① into ②, ② into ③, ③ into ④, and when there is only one problem in each region undivided, so it’s a recursive termination condition.
Starting from the classic examples of recursion
The Hanoi Tower Problem
The Hanoi Tower problem is also a classical recursive problem, which follows:
Hanoi Tower problem: In ancient times, there was a Brahma tower with three seats A, B, and C. There were 64 plates of different sizes on seat A, with the larger ones at the bottom and the smaller ones at the top. A monk wants to move this plate from Block A to Block B, but only one dish can be moved at a time, and in the process of moving, the plates on the three blocks always keep the larger plate at the bottom and the smaller plate at the top.
- If there is only one plate, it is unnecessary to use Tower B and move it directly from A to C.
- If there are two plates, you can first move plate one on plate 2 to B; move plate 2 to C; and move plate 1 to C. It shows that you can move two plates from A to C with the help of B. Of course, you can also carry two plates from A to B with the help of C.
- If there are three plates, then according to the conclusion of 2 plates, two plates on plate three can be moved from A to B with the help of C; we can move plate three from A to C, and A becomes an empty seat; we can move two plates on B to C with the help of seat A.
- By analogy, the above idea can be extended to the case of n plates, viewing the smaller n-1 plates as a whole, which is the subproblem we require. For example, with the help of tower B, we can move the n-1 plates on plate A from A to B with the use of empty tower B. Move the largest plate on A to C, and A becomes empty. Or move n-2 plates on tower B from A to C with the help of empty tower A. And also, move the largest plate to C, and B becomes empty.
Step Climbing Problem
Problem Description.
A person climbs stairs only 1 or 2 steps at a time. Assuming there are n steps, how many different ways does the person climb the stairs?
Let’s start with a simple one, for example, four steps, which the person can climb by climbing 1 step at a time.
Here, think about it: according to the first step, all the ways of walking can be into two categories.
① The first category is the first step took 1 step
② the second category is the first step took two steps
So the n-step walk is equal to the walk after 1 step, n-1 steps, and then add the walk after two steps, n-2 steps.
With the recursive formula, the recursive code is half complete. Then consider the recursive termination condition.
We don’t need to continue the recursion when there is one step, so there is only one way to go.
So f(1) = 1.
This recursive termination condition is insufficient after experimenting with smaller numbers like n = 2 and n = 3.
For n = 2, f(2) = f(1) + f(0). If the recursive termination condition is only one f(1) = 1, then f(2) is unsolvable and the recursion cannot end.
So in addition to f(1) = 1, there is also f(0) = 1, which means there is a way to go 0 steps. So for the sake of understanding, we take f(2) = two as a termination condition, which means that there are two ways to go, one step or two steps.
Summarize as follows
① Assume there is only one step, then there is only one way to go, that is, climb 1 step
② Assume there are two steps, then there are two ways to go, one step to finish or two steps to go
To summarize how to write recursive code by using the above two examples.
1. find the law of how to decompose significant problems into minor problems
2. write recursive formulas through the law
3. Extrapolate the termination condition through the critical point of the recursive formula
4. Translate the recursive formula and termination condition into code
