c++顯式棧如何實現遞歸

本篇文章為大家展示了c++顯式棧如何實現遞歸，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

前言

在大學的課上老師有教過，也就是用循環來實現遞歸，現在自己回顧一下并且做一下記錄。

1. 遞歸

假設有函數A， 和函數B， 函數B是一個遞歸函數， 函數A調用函數B。
這個遞歸的過程分為：

函數A調用函數B，函數A將數據傳給函數B。此時進入到函數B內部，函數B通過傳參拿到函數A傳過來的數據。執行本次調用的操作將新的數據作為參數傳入函數B（遞歸過程， 內部再次執行2~3步驟，以此類推）。退出遞歸結束。

2. 顯式棧實現的思路

由上面的過程可以不難看出，遞歸的過程遵循 后進后出 這樣的一個規律。那么就很容易聯想到具有同樣特征的棧這樣一個數據結構。這里給出顯式棧實現遞歸的思路：
假設已經申請了一個stack的容器，

首先將初始數據壓棧，這個類似于遞歸過程中的函數A最開始調用函數B時將數據傳入的操作。接下來是循環操作，條件是true，也就是死循環， 這個類似于函數B內部一直遞歸調用，至于什么時候結束取決于什么時候遇到遞歸出口；在這個死循環里應該在每次循環時進行一次條件判定，這個條件判定相當于遞歸函數中決定什么時候返回的條件判定；接下來進到循環內部，首先取棧頂數據出來，這類似函數B內部取到了傳參執行 本次的循環的關鍵操作，處理數據的任務將新的數據壓棧，這部分相當于將新的數據作為參數傳入函數B如果觸發了循環退出條件，則退出循環

3. 代碼解析

上面說了具體思路，現在用代碼來說明，首先上遞歸的寫法， 用遍歷二叉樹作為例子。

#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)
{
	//這個時候已經經歷了步驟2， 函數B拿到了數據root
	// 步驟3，執行本次遞歸調用的關鍵操作
	cout << node->data<< endl; 
	// 步驟4，拿到新的數據root->left_child和root->right_child
	//調用函數B
	if (node->left_child) B(node->left_child);
	if (node->right_child) B(node->right_child);
	//步驟5，遞歸結束
}

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

int main()
{
	A();
}

以上步驟3和步驟4的順序不是固定的，他們順序的不同各自構成了不同的樹遍歷方法(先序，中序，后序遍歷)。接下來是顯式棧實現的寫法

#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);  //模擬一顆樹
	stack<Node*> m_stack;
	m_stack.push(&root); //步驟1，將根節點壓棧, 相當于函數A調用函數B時傳參
	while(true)
	{
		if (m_stack.empty())
		{
			break; 
			//這里相當于步驟5,判定循環結束條件, 也可以寫到while條件上
			//為了思路更清晰，所以寫在循環里面，也更好跟遞歸版本進行比較
		}
		//步驟2，取棧頂元素
		Node* current_node = m_stack.top();
		m_stack.pop();
		//步驟3，執行本次循環的關鍵操作
		cout << current_node->data<< endl;
		//步驟4， 拿到新的數據并且壓棧
		if (current_node->left_child)
			m_stack.push(current_node->left_child);
		if (current_node->right_child)
			m_stack.push(current_node->right_child);
	}
}

顯式棧實現的版本里，有一個細節就是取完棧頂數據之后需要將棧頂的數據出棧，這樣才能使用棧是否空來判斷遞歸出口。

上述內容就是c++顯式棧如何實現遞歸，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。