递归与循环的效率迷思

我会带着你远行 2021-12-21 08:43 215阅读 0赞

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

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

简单举个加法的例子(求解前 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%** 左右 ~

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

// C#
    
    // recur version
    long FibonacciRecur(long index)
    {
    	if (index <= 1)
    	{
    		return index;
    	}
    	else 
    	{
    		return FibonacciRecur(index - 1) + FibonacciRecur(index - 2);
    	}
    }
    
    // iter version
    long FibonacciIter(long index)
    {
    	if (index <= 1)
    	{
    		return index;
    	}
    	else 
    	{
    		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;
    	}
    	else 
    	{
    		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;
    			}
    			else 
    			{
    				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;
    				}
    				else
    				{
    					if (child.GetChildCount() > 0)
    					{
    					    s_stack.Push(child);
    					}
    				}
    			}
    		}
    	}
    	
    	return null;
    }

考虑到递归调用的高消耗,似乎我们应该将之前的递归代码改写为这种循环形式,但是 Profile 之后发现,其实循环版本还略慢于递归版本,原因就在于(模拟)调用栈的引入抵消了(甚至超过了)函数调用的开销.

其实一般而言,栈内存的操作消耗都要小于堆内存的操作消耗,上面例子中引入的(模拟)调用栈其实就是一种堆操作,考虑到 CLR(C\#) 的可能影响,我也用 C++ 进行了一样的实现对比,最终结果也是一致的,甚至在 C++ 中实现的循环版本还要显著慢于其递归版本.

还有一个问题之前没有提及,就是代码可读性问题,从我个人经验来讲,递归代码的可读性大体上还是要优于循环代码的.

#### 结论 ####

一般而言,将递归代码改写为循环代码可以提高效率,但是一旦改写过程中引入了堆操作,那么结果往往是相反的.

[Link 1]: https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97
[BFS]: https://zh.wikipedia.org/zh/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
[DFS]: https://zh.wikipedia.org/zh-hans/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2