数据结构与算法--递归（factorial）

什么是递归？

百度百科上的解释是：程序调用自身的编程技巧称为递归（factorial）。

递归是一种应用比较广泛的算法，它通常把一个复杂的问题转化为一个与原问题相似小问题来求解，这样大大的减少了程序的代码量。

举个简单的例子，数学中会有计算阶乘的题目，例如3的阶乘是多少？我们很快能得到答案6。那假如数值更大呢？作为一个程序猿，我们可以使用代码来实现。下面以C语言为例，计算阶乘，代码如下：

#include <stdio.h>

#define FUNCTION_TRUE   1
#define FUNCTION_FALSE  0

void print_loop(void);
long factorial(int n);
long iterative_factorial(int n);

int main(void)
{
   int a = 0;
   long result = 0;

   //print_loop();

   printf("请输入要计算阶乘的数值:");
   scanf("%d",&a);

#if FUNCTION_TRUE
   result = factorial(a);
   printf("%d的阶乘是%ld",a,result);
#else
   result = iterative_factorial(a);
   printf("%d的阶乘是%ld",a,result);
#endif
   return 0;
}


void print_loop(void)
{
    printf("Hello!\n");
    print_loop();
}


long factorial(int n)
{
    if(n == 0)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}
   
    
long iterative_factorial(int n)
{
    int cnt = 0;
    long fac = 1;
    
    for(cnt = 1;cnt <= n;cnt++)
    {
        fac *= cnt;
    }
    
    return fac;
}

上面代码用了两种方式来实现阶乘的计算，一个是使用迭代的方式，使用iterative_factorial函数来实现，另一种是使用递归的方式，使用的是factorial函数。两个函数的切换使用#if--#else--#endif的结构来切换，这个结构在往后的编程中也会经常使用，可以用来注释代码，也可以用来进行函数调用的切换。