算法：求阶乘（递归树）

墨蓝 2023-02-13 12:24 35阅读 0赞

# 阶乘公式推导 #

F(0) = 1  
F(1) = 1 \* 1 = 1 \* F(0)  
F(2) = 2 \* 1 = 2 \* F(1)  
F(3) = 3 \* 2 \* 1 = 3 \* F(2)  
F(n) = n \* F(n-1)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

*  0的阶乘为社么是1
    
     *  阶乘是排列组合的数量， 比如三个东西排列组合有3! (=6)种方式
     *  那么如果没有东西，如何排列组合？
     *  ——那就“不排列组合”。“什么都不做”可以当做一种方式，i.e： 0!=1.

# 解决 #

public static int Fab(int n) {
        
           if (n <= 1){
        
               return 1;
           }
    
           return n * Fab(n - 1);
        }

[递归树][Link 1]如下  
![在这里插入图片描述][20200529131006111.gif]

#include <cstdio>
    #include <string>
    #include <vector>
    #include <sys/stat.h>
    #include <cstring>
    #include <assert.h>
    #include <stack>
    using namespace std;
    
    int Jie(int num){
        
        if(num == 1){
        
            return 1;
        }
    
        return num * Jie(num - 1);
    }
    
    
    int JieStack(int num){
        
        assert(num > 0);
        std::stack<int> stack;
        stack.push(num);
    
        int data = 0, ans = 1;
        while (!stack.empty()){
        
            data = stack.top();
            stack.pop();
            if(data == 1){
        
                ans = ans * data;
            }else{
        
                ans = ans * data;
                stack.push(data - 1);
            }
        }
    
        return ans;
    }
    
    
    int main(int argc,char **argv){
        
    
        printf("%d\n", Jie(5));
        printf("%d\n", JieStack(5));
    
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200529130627104.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[Link 1]: https://visualgo.net/zh/recursion
[20200529131006111.gif]: https://img-blog.csdnimg.cn/20200529131006111.gif