1. What is recursion?
An object is said to be recursive if it is described through its own definition. That is, these objects are defined inductively from the simplest concepts of its kind. In mathematics and informatics there are many such subjects. VD:
The natural number is defined as follows:
0 is a natural number If k is a natural number then k+1 is also a natural number
Accordingly, we will have: 1=0+1 is a natural number, 2=1+1 is also a natural number, etc. Just like that, we will define other larger natural numbers. Therefore, natural numbers are recursive in nature.
You are viewing: What is recursion
– Factorial definition of n (n!) :
When n=0, we have 0!=1When n>0, we have n!=(n-1)! xn
Thus, we infer: 1! = 0! x 1, 2! = 1! x 2,… –> factorial is also a recursive concept.
2. Recursion problem
Those are recursive problems. That is, these problems can be decomposed into smaller, simpler problems that have the same form as the original problem. Smaller problems are decomposed into smaller problems. Just like that, the decomposition only stops when the subproblem is so simple that the result can be immediately deduced without having to decompose anymore. We have to solve all the subproblems and then combine those results to get the solution to the original big problem. Such a method of problem decomposition is called “devide and conquer”, which is a form of recursion.
3. Recursion in programming
A function is said to be recursive if within its body there is a call to itself. Sounds absurd, right? How can a function call it forever, because if so, it will create an endless loop. But in practice, a recursive function that always has a condition should not be called an “anchor point”. When the anchor point is reached, the function will no longer call itself.
When called, the recursive function is usually passed one parameter, usually the size of the original large problem. After each recursive call, the parameter will become smaller, to reflect the already smaller and simpler problem. When the parameter reaches a minimum value (at the anchor point), the function terminates.
In programming, a problem to be solved by recursion must be a recursive problem itself. That is, the problem can be reduced to the same but simpler problem.
4. Some classic recursion problems
a. Factorial math problem
Let n be a natural number (n>=0). Calculate the factorial of n (n!) knowing that 0!=1 and n!=(n-1)! x n.
– By assumption, we have: n! = (n-1)! x n. So :
To calculate n! we need to compute (n-1)!To compute (n-1)! we have to calculate (n-2)!…
– And so on, until the case 0!. Then we immediately get the result 1, no need to calculate through another intermediate result.
Install on C# :
– Here, the main anchor point is n=0. After each recursive call, n will decrease by 1 until the anchor point is reached.
b. Fibonacci series
The Fibonacci sequence is an infinite sequence of natural numbers. The nth Fibonacci number, symbol F(n), is defined as follows:
F(n) = 1, if n=1 or n=2F(n) = F(n-1) + F(n-2), if n>=3
Request : calculate the nth number of fibonacci given n.
See more: What is a Profile – Meaning of Profile in Vietnamese
– With n
– With n>=3 :
To calculate F(n) we have to calculate F(n-1) and F(n-2). To calculate F(n-1) we have to compute F(n-2) and F(n-3), and to calculate F(n-2) we have to calculate F(n-3) and F(n-4).…and so on until n=1 and n=2.
Install on C# :
– Below is the recursion diagram when calling the function to calculate F(5) :
Thus, the problem was solved simply by recursion.
c. Problem “Tower of Hanoi” (Tower of Ha Noi)
This is a very famous and classic problem, very suitable for illustrating a recursive algorithm. Here is the content of the problem:
There are 3 piles marked A, B, C and n disks respectively. These discs come in different sizes and each has a hole in the middle for the stake. Initially, the disks are located on pole A, in which, the small disk is always on the larger disk.
Request : Move n disks from pole A to destination pole C with the following conditions:
+ Only 1 disc can be transferred at a time
During transfer, the small disk must always be on top of the larger disk.
+ It is allowed to use pile B as an intermediate pile
Analysis: We will consider the cases of n
– The simplest case, n=1, we just need to move 1 disk from pole A to pole C.
– A little more, n=2, we move the smallest disk to pole B, move the other disk to pole C, and finally move the small disk on pole B to pole C.
– Now we consider n disks (n>2). Suppose we already have a way to move n-1 disks from one pole to another. Thus, to move n disks from the source pile to the destination pole, we need to move n-1 disks from the source pole to the intermediate pole. Then move the largest disk from the source pole to the destination pole. Finally, move n-1 from the intermediate pole to the destination pole.
Install using C# :
public static void ThapHaNoi(int n, char source, char dich, char tgian) //anchor if (n == 1) Console.WriteLine(“Convert 1 location 0 to 1”, source, translate ); else //move n-1 disks from the source pole to the intermediate pole, //take the destination pole as a secondary pole ThapHaNoi(n – 1, source, tgian, translate); //move the rest from source to destination Console.WriteLine(“Transfer 1 dia from 0 to 1”, source, translate); //transfer n-1 from intermediate pile to destination pile, //take source pile as intermediate pile ThapHaNoi(n – 1, tgian, dich, source);
The above function is responsible for transferring n disks from column source to the pile translateusing pile tgian make auxiliary poles. Here we denote the columns as A, B, C, so we will use the char type.
See also: What is hand flower – Meaning of hand flower
Thus, we have learned the basics of recursion. These are just simple recursive problems. There are many other problems and techniques that use recursion.