递归和动态规划，C语言实现

柔光的暖阳◎ 2023-03-01 05:43 39阅读 0赞

这一章讲解递归和动态规划。其中递归中有一个分支称之为“分治”，这是提高软件效率的重要方法，例如著名的快速排序算法、二分查找等就是利用了递归中的“分治”思想；动态规划是通向编程高手的十大算法之一。

递归：编程语言中，函数f(n)直接或间接调用函数本身，则该函数称为递归函数。递归计算过程：把f(n)用f(n -1)或者f(n/2)等表达。然后重复的调用f(n)。当n为很小的数时，直接给出结果。计算机会计算出最终结果。  
动态规划：基本思想是将待求解问题分解成若干个子问题，每个子问题可能都要求1个相同问题的解。先求解子问题，然后根据这些子问题的解得到原问题的解。使用动态规划一定要注意一点：后面的计算不能导致前面的结果发生变化，否则就不能使用动态规划。  
*看不懂上面的描述？那就看下面的代码吧。*

## 递归和动态规划代码描述 ##

void fun1(int n) //最简单的for循环计算1~n的累加和
    {
        
    	int sum = 0;
    	for (int i = 0; i <= n; i++)
    	{
        
    		sum += i;
    	}
    	printf(“sum = %d”, sum);
    }

这是用来计算1 + 2 + 3 + … + n的函数。代码非常简单，就是用一个for循环将循环变量i的值累加到sum中。如果n = 100，则最后输出结果：5050。代码的时间复杂度为O(N)。  
我们来分析一下这个代码：每循环一次，sum的值就修改一次，所以变量sum的值一共要修改100次。这里其实就蕴含了动态规划的基本思想：利用上一次的结果，计算这一次的数据。为了把问题说的更清晰，我们把代码改写成下面的函数：

void fun2(int n) //动态规划
    {
        
    	int arr[100]; //计算得到的中间结果保存在数组arr中
    	arr[0] = 0; // arr[0]的默认值为0
    	int sum = 0; //sum的起始值为0
    
    	//在这个函数中，每次循环得到的数据放在arr[i]中，
    	//下一轮循环时，直接用arr[i]的值计算sum即可。
    	for (int i = 1; i <= n; i++)
    	{
        
    		sum = arr[i - 1] + i; //用arr[i - 1]的值计算sum
    		arr[i] = sum; //把sum的值保存在arr[i]中
    	}
    	printf(“sum = %d”, sum);
    }

fun1()中，每次循环得到的数据放在sum中。而在fun2()中，每次计算的值都放在arr中，直接用arr\[i - 1\]的值即可计算sum。看了这个代码之后，再来体会动态规划的思想是不是觉得很简单呢？  
动态规划中，最重要的可能是推导出 f(n)与f(n - 1)或f(n / 2)的关系式了，另外，一定要确认后面的计算不会导致之前的计算结果发生变化。  
在fun2()中，f(n)与f(n - 1)的表达式为：f(n) = f(n - 1) + n。利用这个表达式，除了动态规划算法，我们也可以用递归方式进行计算：

void fun3(int n)
    {
        
    	if (n <= 0) //递归的出口
    	{
        
    		return 0;
    	}
    	return fun3(n - 1) + n; //递归
    }

上述三种方式的时间复杂度都是O(N)。是不是还有更高效的算法？请看下一节：递归提高效率的方式。

## 递归提高效率的方式 ##

前面提高f(n) 与f(n - 1) 的关系为：f(n) = f(n - 1) + n。也就是说要计算f(n)，就必须知道f(n - 1)的值，要计算f(n - 1)，就必须知道f(n - 2)的值…这样类推，就可以知道一共要计算n次，所以时间复杂度是O(N)。  
如果我们能找到f(n) 与 f(n / 2)的关系，那么n的值每次都减少一半，这样很快就可以减少到1。时间复杂度: O(logN)。  
如果n为奇数，可以用之前的关系式：f(n) = f(n - 1) + n；  
如果n为偶数，可以用关系式：f(n) = 4 \* f(n / 2) - n / 2 (推导过程见本章最后的注释)。利用这两个公式，我们编写如下代码：

int fun5(int n)
    {
        
    	if (n == 1 || n == 0)
    	{
        
    		return n; //递归的出口
    	}
    
    	//分两种情况进行讨论
    	if (n % 2 == 0) //偶数
    	{
        
    		return 4 * fun5(n / 2) - n / 2; //递归
    	}
    	else //如果n是奇数，那么n - 1就是偶数。
    	{
        
    		//所以n为奇数时，使用这个关系式: f(n) = f(n - 1) + n
    		return fun5(n - 1) + n; //递归
    	}
    }

我们对这段代码验证一下：

f(100) = 4 * f(50) - 100 / 2
    f(50) = 4 * f(25) - 50 / 2
    f(25) = f(24) +25 = 4 * f(12) - 24 / 2 + 25
    f(12) = 4 * f(6) - 12 / 2
    f(6) = 4 * f(3) - 6 / 2
    f(3) = f(2) + 3 = 4 * f(1) - 2 / 2  + 3
    f(1) = 1 (递归的出口)

一共只需要计算 = logN = 7次。效率确实要比前面三种方式 (计算100次) 高很多。如果n是1000，只需要计算10次，如果n是10000，只需要计算13次。我们发现随着n的增大，这种方式的效率相对于前面三种方式越来越高。

## 动态规划的缺陷 ##

我们找到了f(n) 与 f(n / 2)的关系，那么能不能基于f(n) = 4 \* f(n / 2) - n / 2这个公式编写动态规划代码呢？我们模拟一下计算过程：

f(1) = 1
    f(2) = 4 * f(1) - 2 / 2
    f(4) = 4 * f(2) - 4 / 2
    f(8) = 4 * f(4) - 8 / 2
    f(16) = 4 * f(8) - 16 / 2
    f(32) = 4 * f(16) - 32 / 2
    f(64) = 4 * f(32) - 64 / 2
    f(128) = 4 * f(64) - 128 / 2

我们发现用这个方式无法计算f(100)。原因是：用递归方式计算时，发生两次调用f(n) = f(n - 1) + n，而动态规划代码不知道什么时候调用这个关系式。所以动态规划不能利用f(n) = 4 \* f(n / 2) - n / 2这个公式。

## 总结 ##

1、递归：把大问题分解成小问题后进行求解；递归会占用大量内存，且有可能超出最大递归次数。  
2、动态规划：用小问题的解，解决大问题。注意，一定要确认后面的计算不会导致之前的计算结果发生改变才能使用动态规划。  
3、递归和动态规划正好是两种相反的思路。这两种方式的时间复杂度：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
4、关于f(n) = 1 + 2 + 3 + … + n的计算，用累加公式 f(n) = n \* (n + 1) / 2的效率最高，时间复杂度为O(1)。但这不是本文的研究重点。

## 注释 ##

已知f(n) = 1 + 2 + 3 + … + n，推导f(n) 与f(n / 2) 的关系式：  
关系式1推导如下：  
f(n) = 1 + 2 + 3 + … + n = 1 + 2 + 3 + … + n/2 + (n/2 + 1)+ (n/2 + 2) … + (n/2 + n/2)  
如果n为偶数，前一半为：f(n/2) = 1 + 2 + 3 + … + n/2  
后一半为(n/2 + 1)+ (n/2 + 2) … + (n/2 + n/2) = n/2 \* n/2 + (1 + 2 + 3 + … + n/2)  
= n \* n / 4 + f(n/2)  
则f(n) = f(n/2) + n \* n / 4 + f(n/2) = 2 \* f(n/2) + n \* n / 4

关系式2推导如下：  
如果n为偶数  
f(n) = 1 + 2 + 3 + … + n = (2 + 4 + 6 +…+ n) + (1 + 3 + 5 + … + n-1)  
= (2 + 4 + 6 +…+ n) + (2 + 4 + 6 +…+ n) - n/2  
= 2 \* (2 + 4 + 6 +…+ n) - n/2 = 2 \* 2 \* (1 + 2 + 3 + … + n/2) - n/2  
= 4 \* f(n/2) - n/2

下一小节，我们将对动态规划和 (或) 递归的应用进行举例说明，老规矩，所有代码都是用C语言实现。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/0656d5ce9fd84a43a1df216e79b1c5a8.png