为何基于二叉树的动态规划阶乘实现比普通递归更慢？

我刚接触动态规划，尝试用其求解阶乘问题，采用二叉树作为底层数据结构。在联想Ideapad3（Arch Linux系统）上使用chrono库计时，开启O3优化后发现普通递归实现的运行速度比该动态规划实现更快。

测试代码 #

#include<iostream>
#include <chrono>
using namespace std;
using namespace chrono;

class Fact{
    struct Node {
        unsigned long long data, value;
        Node* Rptr;
        Node* Lptr;
        Node(): data(0), value(0), Rptr(nullptr), Lptr(nullptr) {}
        Node(int d, int v): data(d), value(v), Rptr(nullptr), Lptr(nullptr) {}
    };
    Node* root;
    public:
        Fact(): root(nullptr) {}
        Node* inTree(Fact::Node* ptr, int data);
        Node* insertInTree(Fact::Node* ptr, int data, int value);
        unsigned long long findFact(int num);
        void deleteTree(Node* root) {
            if (root == NULL) {
                return;
            }
            deleteTree(root->Lptr);
            deleteTree(root->Rptr);
            delete root; 
        }

        ~Fact() {
            deleteTree(root);
        }
};

unsigned long long factorial(int n) {
    return (n < 1) ? 1 : n*factorial(n-1);
}

int main() {
    Fact fact;

    //DP solution
    auto start = high_resolution_clock::now();
    auto answer = fact.findFact(20);
    auto stop = high_resolution_clock::now();
    cout << "Factorial of 20 is:" << answer << endl;
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken: " << duration.count() / 1000.0 << " milliseconds" << endl;

    //Recursion
    answer = 0;
    start = high_resolution_clock::now();
    answer = factorial(20);
    stop = high_resolution_clock::now();
    cout << "Factorial of 20 is:" << answer<< endl;
    duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken: " << duration.count() / 1000.0 << " milliseconds" << endl;
    return 0;
}

unsigned long long Fact::findFact(int num) {
    Node* temp;
    if(num <= 1) return 1;
    else if((temp = inTree(root,num))) return temp->value;
    else {
        long long res = num * findFact(num - 1);
        insertInTree(Fact::root,num, res);
        return res;
    }
}

Fact::Node* Fact::insertInTree(Fact::Node* ptr, int data, int value) {
    if (ptr == NULL) {
        return new Node(data, value);
    }

    if (data < ptr->data) {
        ptr->Lptr = insertInTree(ptr->Lptr, data, value);
    } else if (data > ptr->data) {
        ptr->Rptr = insertInTree(ptr->Rptr, data, value);
    }
    return ptr;
}

Fact::Node* Fact::inTree(Fact::Node* ptr, int data) {
    if(!ptr) return nullptr;
    else {
        if(ptr->data == data) return ptr;
        else {
            if(data > ptr->data) return inTree(ptr->Rptr, data);
            else return inTree(ptr->Lptr, data);
        }
    }
}

开启O3优化后的运行输出 #

[firefly@machine]$ g++ -O3 factorial.cpp -o fact
[firefly@machine]$ ./fact 
Factorial of 20 is:2432902008176640000  
Time taken: 0.001 milliseconds          //Time for DP-sol
Factorial of 20 is:2432902008176640000  
Time taken: 0 milliseconds              //Time for recursion

性能差异的原因 #

• 递归被编译器完全优化：O3优化级别下，编译器会对逻辑简单的递归进行深度优化。对于factorial(20)，编译器能直接在编译期计算出常量结果，运行时无需任何计算或递归调用，直接返回预存的值，所以计时显示为0毫秒。即使是更大的n，编译器也会执行尾递归消除，把递归转换成循环，消除函数调用开销。

• 二叉树DP的额外开销过大：你的DP实现依赖二叉树缓存结果，但单次计算20!时，缓存完全没发挥作用——每个n的阶乘都是第一次计算，需要执行：

  • 递归式的二叉树查找，带来额外的函数调用开销；
  • 每次计算后执行new Node动态分配内存，内存分配是系统级操作，耗时远大于阶乘计算本身；
  • 二叉树节点分散在堆内存中，CPU缓存无法有效命中，进一步降低执行效率。

• DP的缓存优势未被触发：动态规划的核心优势是避免重复计算，但本次测试只计算了一次20的阶乘，所有中间结果都是首次计算，缓存的插入操作完全是冗余开销。只有当多次重复计算不同n的阶乘时，缓存才能减少重复计算，体现出优势。

• 类型转换的隐性开销：代码中存在多处类型不一致的情况，比如findFact中用long long存储结果，插入节点时又转成int，再存储为unsigned long long，这些隐式转换会带来微小的额外开销，叠加后也会影响整体速度。

内容的提问来源于stack exchange，提问作者Vishwas MIshra