递归与循环的效率迷思-蒲公英云

递归与循环的效率迷思

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

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

简单举个加法的例子(求解前 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;
    }
    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;
}