Recursion and System Stack

递归是计算机科学中一个非常重要的概念，对于斐波那契那种比较简单的递归，分析起来比较容易，但是由于二叉树涉及指针操作，所以模仿下遍历过程中系统栈的情况。

以二叉树中序遍历为例演示：

//二叉树定义

struct TreeNode {

	TreeNode* left;

	TreeNode* right;

	int val;

	TreeNode(int x) :val(x), left(NULL), right(NULL) {}

};

中序遍历的递归实现：

假设二叉树如图所示：

其中序遍历序列为\(2413\)，可以在VS中用单步调试的方法跟踪相应的变量：

当root==NULL(root指向2的左孩子)时，此时的系统栈（将1和2都压栈，因为中序遍历需要先访问左孩子）：

这时if不成立，执行83行的return语句，接着退栈，回到78行，此时的root指向2(因为此时程序已经来到了新的栈顶)，并且向这个新栈顶返回了一个空的seq：

接着执行79行(因为这是上一个函数return的，所以不会再一次执行78行)，将2存入seq中；

执行80行（root指向4），进而执行78行，root指向4的左孩子，此时的系统栈（很明显可以看到从栈底到栈顶依次存放根结点到当前root结点的路径上的结点）：

同样，执行return语句，退栈，将seq(里面只有2)返回到这一层，这一层的root指向4，接着将4存入seq；

到80行，调用inOrder()使得root指向4的右孩子，右孩子为空，所以返回并退栈，root重新指向4，此时80行执行完毕，整个if执行完毕，返回seq并退栈，root返回到了2，以2为根结点的子树中序遍历完毕，系统栈：

继续执行，return到78行，root指向1，将1存入seq，以此类推，就可以得到整个的遍历序列。

最关键的是：之所以要递归调用inOrder，就是因为现在还不想访问当前的结点（对于中序，要先找到最左边的结点），所以通过递归的方式将当前暂时不想访问的结点压入系统栈，找到了想访问的结点后，访问它并利用退栈操作返回父结点。

顺便记录一些经典的递归程序：

bool isPalindrome(string s) {

	if (s.length() <= 1)

		return true;

	return s[0] == s[s.length() - 1] &&

		isPalindrome(s.substr(1, s.length() - 2));

}

const int NotFound = -1;

int BSearch(vector<string>& v, int start, int stop, string key) {

	if (start > stop) return NotFound;

	int mid = (start + stop) / 2;

	if (key == v[mid])

		return mid;

	else if (key > v[mid])

		return BSearch(v, mid + 1, stop, key);

	else

		return BSearch(v, start, mid - 1, key);

}

int C(int n, int k) {

	if (n == k || k == 0)

		return 1;

	else

		return C(n - 1, k) + C(n - 1, k - 1);

}

void permute(string soFar, string rest) {

	if (rest == "")

		cout << soFar << endl;

	else {

		for (int i = 0; i < rest.length(); ++i) {

			string next = soFar + rest[i];

			string remaining = rest.substr(0, i) + rest.substr(i + 1);

			permute(next, remaining);

		}

	}

}

// v2

void per(vector<int>& nums, int n, int d, vector<bool>& used, vector<int>& cur, vector<vector<int>>& ans) {

	if (n == d) {

		ans.push_back(cur);

		return;

	}

	for (int i = 0; i < nums.size(); ++i) {

		if (used[i])

			continue;

		used[i] = true;

		cur.push_back(nums[i]);

		per(nums, n, d + 1, used, cur, ans);

		cur.pop_back();

		used[i] = false;

	}

}

void com(vector<int>& nums, int n, int d, int start, vector<int>& cur, vector<vector<int>>& ans) {

	if (n == d) {

		ans.push_back(cur);

		return;

	}

	for (int i = start; i < nums.size(); ++i) {

		cur.push_back(nums[i]);

		com(nums, n, d + 1, i + 1, cur, ans);

		cur.pop_back();

	}

}

void subsets(string soFar,string rest) {

	if (rest == "")

		cout << soFar << endl;

	else {

		// add to subset, remove from rest, recur

		subsets(soFar + rest[0], rest.substr(1));

		// do not add to subset, remove from rest, recur

		subsets(soFar, rest.substr(1));

	}

}

// one root

func solve(root)

{

    if(root == null)  return ...

    if f(root) return ...

    l = solve(root->left);

    r = solve(root->right);

    return g(root, l , r);

}

// two roots

func solve(p, q)

{

    if(p == null && q == null)  return ...

    if f(p, q)  return ...

    l = solve(p.child, q.child);

    r = solve(p.child, q.child);

    return g(p, q, l, r);

}

巴特西

Recursion and System Stack

最新文章

热门文章