递归与循环的效率迷思

本文简单比较了一下相同逻辑下,递归实现和循环实现的效率差异

已经不记得最初是从哪里获取的信息了,自己总有一个印象是递归的效率比循环差,因为递归有很大的函数调用开销,再加上递归可能存在的堆栈溢出问题(本文暂不考虑该问题),所以书写代码时还是尽量使用循环为好.

简单举个加法的例子(求解前 n 个自然数的和):

// C#
// recur version
int AddRecur(int val)
	if (val > 0)
		return val + AddRecur(val - 1);
	return 0;
// iter version
int AddIter(int val)
	var ret = 0;
	for (int i = 1; i <= val; ++i)
		ret += i;
	return ret;
}

简单 Profile 一下,发现循环版本比递归版本要快 64% 左右 ~

再举个耳熟能详的例子: 斐波那契数列

// C#
// recur version
long FibonacciRecur(long index)
	if (index <= 1)
		return index;
		return FibonacciRecur(index - 1) + FibonacciRecur(index - 2);
// iter version
long FibonacciIter(long index)
	if (index <= 1)
		return index;
		long pre = 0;
	    long cur = 1;
	    long next = 0;
	    for (long i = 2; i <= index; ++i)
	    	// calc next
	    	next = pre + cur;
	    	// update pre and cur
	    	pre = cur;
	    	cur = next;
	    return next;
}

继续 Profile 一下,发现循环版本比递归版本要快了 96% 左右 ! 不过稍有递归经验的朋友都会看出,上面的递归实现会做很多的重复计算,更好的方式就是缓存一下中间的计算结果:

// C#
Dictionary<long, long> s_buffer = new Dictionary<long, long>();
long FibonacciRecur(long index)
	if (index <= 1)
		return index;
		long pre = 0;
		if (!s_buffer.TryGetValue(index - 1, out pre)) 
		    pre = FibonacciRecur(index - 1);
            s_buffer[index - 1] = pre;		    
		long cur = 0;
		if (!s_buffer.TryGetValue(index - 2, out cur))
		    cur = FibonacciRecur(index - 2);
            s_buffer[index - 2] = cur;		    
		return pre + cur;
}

改动之后,循环版本比递归版本就只快 64% 左右了 ~

试验到现在,似乎都印证了我之前的印象: 递归比循环慢,写代码就要写循环~

我们最后来看个真实的(也更复杂的)示例:查找指定名字的子节点(假设我们有一颗树形结构的节点树,给出根节点,查找某个指定名字的子节点)

以下是一个简易的树形结构实现:

// C#
public class Node 
	string m_name;
	List<Node> m_children = new List<Node>();
	public Node(string name, params Node[] children)
		m_name = name;
		m_children.AddRange(children);
	public string GetName()
		return m_name;
	public int GetChildCount()
		return m_children.Count;
	public Node GetChild(int index)
		if (index >= 0 && index < m_children.Count) 
			return m_children[index];
		return null;
}

查找树形结构的指定节点一般可以采用 BFS 或 DFS ,这里我们使用 DFS :

// C#
Node FindChildRecur(Node parent, string name)
	if (parent != null)
		var childCount = parent.GetChildCount();
		for (int i = 0; i < childCount; ++i)
			var child = parent.GetChild(i);
			if (child.GetName() == name) 
				return child;
				var childNode = FindChildRecur(child, name);
				if (childNode != null)
					return childNode;
	return null;
}

如果要将上面的递归代码改为循环代码,方法就没有之前那么简明了,需要我们自行来模拟调用栈:

// C#
Stack<Node> s_stack = new Stack<Node>();
Node FindChildIter(Node parent, string name)
	if (parent != null)
		s_stack.Clear();
		s_stack.Push(parent);
		while (s_stack.Count > 0)
			var curParent = s_stack.Pop();
			var childCount = curParent.GetChildCount();
			for (int i = childCount - 1; i >= 0; --i)
				var child = curParent.GetChild(i);
				if (child.GetName() == name)
					return child;
					if (child.GetChildCount() > 0)
					    s_stack.Push(child);