c++顯式棧實現遞歸介紹

Posted on by

前言

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

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++顯式棧實現遞歸介紹的文章就介紹到這瞭,更多相關c++遞歸內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：