C++ recursive algorithm example code

  • 2020-06-01 10:25:16
  • OfStack

Recursive algorithm, summed up with the following characteristics:

Feature 1 it has a basic part, that is, directly satisfy the condition, output
Feature 2 it has a recursive part, that is, by changing the cardinality (that is, n), it gradually makes n meet the conditions of the basic part, thus output
Feature 3 in the process of implementation, it adopts the idea of divide-and-conquer:
Divide the whole into parts, and always start with the smallest part (the basic part) (output). The principle behind this is that when the whole recurses to the part, the information of the whole will be retained, and the output of the part that meets the condition will be backtracked to the whole, so that the whole output will be used.
Feature 4 for each step operation, the whole will regard the part as a necessary step, so as to realize the completion of the whole step


This problem is to use the enumeration of the train of thought to judge a specified logical expression is never true

So the first thing they're saying is there's no more than five logical variables, there's five operations

Definitions of K, A, N, C, and E
     w  x   Kwx   Awx    Nw   Cwx   Ewx
  1  1   1   1    0   1   1
  1  0   0   1    0   0   0
  0  1   0   1    1   1   0
  0  0   0   0    1   1   1

Among them

K &
A |
N !
C - >
E with or

One of C we can use! A | B implementation

E implements using ==

The main difficulty in this problem does not lie in the way our statement is calculated

The difficulties in 1:
Recursive solution of expression, here is really has a profound understanding of the power of recursion, ontology approach we really leave the recursion, our approach is the beginning of a 1 characters enumeration recursive, each character ceding 10, 5 kinds of variables, 5 kinds of operators, here we add 1 indicator variables represent our current position and depth of the recursion, we don't have to set our recursive termination conditions, because we are the expression of ensure the 1 set is correct, our calculation results 1 set is there will be a return value, our calculation result is 1 layer 1 returns

The difficulties in 2:

Bit operations, subject if you don't use an operation, we need to write at least five layer cycle to simulate all of the variables of our situation, this is too low, we will all variables encapsulated into a one byte of memory, every time an operation is utilized to extract the relevant position's Numbers (although we all is not the expression, but at least not wrong)


using namespace std;
int pos=0;
string data;
bool cal(int i)
	int t=pos++;
		case 'p':
			return (i >> 4)&1;
		case 'q':
			return (i >> 3)&1;
		case 'r':
		  return (i >> 2)&1;
		case 's':
		  return (i >> 1)&1;
		case 't':
		  return i&1;
		case 'K':
		  return cal(i) & cal(i);
		case 'A':
		  return cal(i) | cal(i);
		case 'N':
			return !cal(i);
		case 'C':
			return !cal(i) | cal(i);
		case 'E':
			return cal(i) == cal(i);
bool isTautology()
	for(int i=0;i<=31;i++)
		if(cal(i)) continue;
		else return false;
	return true;
int main()
		if(isTautology()) cout<<"tautology"<<endl;
		else cout<<"not"<<endl;
	return 0;


This is the article on the C++ recursive algorithm example code all content, hope to help you. Please refer to: C++ function pointer details and code sharing, C/C++ compiler optimization introduction, etc., if you have any questions, please feel free to leave a message, welcome to discuss. Thank you for your support!

Related articles: