前言

在大學(xué)的課上老師有教過(guò)，也就是用循環(huán)來(lái)實(shí)現(xiàn)遞歸，現(xiàn)在自己回顧一下并且做一下記錄。

1. 遞歸

假設(shè)有函數(shù)A， 和函數(shù)B， 函數(shù)B是一個(gè)遞歸函數(shù)， 函數(shù)A調(diào)用函數(shù)B。
這個(gè)遞歸的過(guò)程分為：

函數(shù)A調(diào)用函數(shù)B，函數(shù)A將數(shù)據(jù)傳給函數(shù)B。此時(shí)進(jìn)入到函數(shù)B內(nèi)部，函數(shù)B通過(guò)傳參拿到函數(shù)A傳過(guò)來(lái)的數(shù)據(jù)。執(zhí)行本次調(diào)用的操作將新的數(shù)據(jù)作為參數(shù)傳入函數(shù)B（遞歸過(guò)程， 內(nèi)部再次執(zhí)行2~3步驟，以此類推）。退出遞歸結(jié)束。

2. 顯式棧實(shí)現(xiàn)的思路

由上面的過(guò)程可以不難看出，遞歸的過(guò)程遵循 后進(jìn)后出 這樣的一個(gè)規(guī)律。那么就很容易聯(lián)想到具有同樣特征的棧這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)。這里給出顯式棧實(shí)現(xiàn)遞歸的思路：
假設(shè)已經(jīng)申請(qǐng)了一個(gè)stack的容器，

首先將初始數(shù)據(jù)壓棧，這個(gè)類似于遞歸過(guò)程中的函數(shù)A最開(kāi)始調(diào)用函數(shù)B時(shí)將數(shù)據(jù)傳入的操作。接下來(lái)是循環(huán)操作，條件是true，也就是死循環(huán)， 這個(gè)類似于函數(shù)B內(nèi)部一直遞歸調(diào)用，至于什么時(shí)候結(jié)束取決于什么時(shí)候遇到遞歸出口；在這個(gè)死循環(huán)里應(yīng)該在每次循環(huán)時(shí)進(jìn)行一次條件判定，這個(gè)條件判定相當(dāng)于遞歸函數(shù)中決定什么時(shí)候返回的條件判定；接下來(lái)進(jìn)到循環(huán)內(nèi)部，首先取棧頂數(shù)據(jù)出來(lái)，這類似函數(shù)B內(nèi)部取到了傳參執(zhí)行 本次的循環(huán)的關(guān)鍵操作，處理數(shù)據(jù)的任務(wù)將新的數(shù)據(jù)壓棧，這部分相當(dāng)于將新的數(shù)據(jù)作為參數(shù)傳入函數(shù)B如果觸發(fā)了循環(huán)退出條件，則退出循環(huán)

3. 代碼解析

上面說(shuō)了具體思路，現(xiàn)在用代碼來(lái)說(shuō)明，首先上遞歸的寫(xiě)法， 用遍歷二叉樹(shù)作為例子。

#include<iostream>
using namespace std;
class Node
{
public:
	int value;
	Node* left_child;
	Node* right_child;
	Node(int data)
	{
		this->data = data;
		this->left_child = nullptr;
		this->right_child = nullptr;
	}
};

void B(Node* node)
{
	//這個(gè)時(shí)候已經(jīng)經(jīng)歷了步驟2， 函數(shù)B拿到了數(shù)據(jù)root
	// 步驟3，執(zhí)行本次遞歸調(diào)用的關(guān)鍵操作
	cout << node->data<< endl; 
	// 步驟4，拿到新的數(shù)據(jù)root->left_child和root->right_child
	//調(diào)用函數(shù)B
	if (node->left_child) B(node->left_child);
	if (node->right_child) B(node->right_child);
	//步驟5，遞歸結(jié)束
}

void A()
{
	Node root(10);  //模擬一顆樹(shù)
	B(&root); //步驟1，傳參
}

int main()
{
	A();
}

以上步驟3和步驟4的順序不是固定的，他們順序的不同各自構(gòu)成了不同的樹(shù)遍歷方法(先序，中序，后序遍歷)。接下來(lái)是顯式棧實(shí)現(xiàn)的寫(xiě)法

#include<iostream>
#include<stack>
using namespace std;
class Node
{
public:
	int value;
	Node* left_child;
	Node* right_child;
	Node(int data)
	{
		this->data = data;
		this->left_child = nullptr;
		this->right_child = nullptr;
	}
};

int main()
{
	Node root(10);  //模擬一顆樹(shù)
	stack<Node*> m_stack;
	m_stack.push(&root); //步驟1，將根節(jié)點(diǎn)壓棧, 相當(dāng)于函數(shù)A調(diào)用函數(shù)B時(shí)傳參
	while(true)
	{
		if (m_stack.empty())
		{
			break; 
			//這里相當(dāng)于步驟5,判定循環(huán)結(jié)束條件, 也可以寫(xiě)到while條件上
			//為了思路更清晰，所以寫(xiě)在循環(huán)里面，也更好跟遞歸版本進(jìn)行比較
		}
		//步驟2，取棧頂元素
		Node* current_node = m_stack.top();
		m_stack.pop();
		//步驟3，執(zhí)行本次循環(huán)的關(guān)鍵操作
		cout << current_node->data<< endl;
		//步驟4， 拿到新的數(shù)據(jù)并且壓棧
		if (current_node->left_child)
			m_stack.push(current_node->left_child);
		if (current_node->right_child)
			m_stack.push(current_node->right_child);
	}
}

顯式棧實(shí)現(xiàn)的版本里，有一個(gè)細(xì)節(jié)就是取完棧頂數(shù)據(jù)之后需要將棧頂?shù)臄?shù)據(jù)出棧，這樣才能使用棧是否空來(lái)判斷遞歸出口。

到此這篇關(guān)于c++顯式棧實(shí)現(xiàn)遞歸介紹的文章就介紹到這了,更多相關(guān)c++遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論