---
# System prepended metadata

title: Recursive 布林變數組合
tags: [Data Structure]

---

# Recursive 布林變數組合 
###### tags: `Data Structure`
新手對於遞迴的想法
這個題目對於剛接觸遞迴的我花了兩天在思考這個題目
```
#include <iostream>
#include <cstdlib>
#include <vector>
int count = 0;
template<typename T>
void booleanCombi(T vec, int i, int n) {
	count++;
	if(i == n) {
		std::vector<int>::iterator begin = vec.begin();
		std::vector<int>::iterator end = vec.end();
		std::vector<int>::iterator it;
		for(it = begin; it != end; it++) {
			std::cout << *it; 
		}
		std::cout << std::endl;
	}else {
		vec.push_back(0);
		booleanCombi(vec, i+1, n);
		vec.pop_back();
		vec.push_back(1);
		booleanCombi(vec, i+1, n);
		vec.pop_back();
	}
}

int main(void) {
	std::vector<int> vec;
	booleanCombi(vec, 0, 3);
	std::cout << count << std::endl;
	
	system("pause");
	return 0;
}
```
## Output
000
001
010
011
100
101
110
111

## 使用c++ STL實作
遞迴的想法在於先想出你的功能有什麼樣的重複性，
可以使得用不斷呼叫函數來完成。
再來是終止點，到甚麼條件下會終止遞迴。

首先先使用C++ vector
將vector傳入booleanCombi()後判斷容器內資料
如果沒有到我們的要求，就增加布林值0
再重複呼叫booleanCombi()
直到i == n 時我們輸出STL vector
並且將之前增加的布林值pop_back
輸入布林值1，持續反覆...

使用 STL 的動態陣列會比較方便
當然要自己手動刻也是可以







