简介

此模块为学校数据结构必修课学习内容的记录与分享

全文大体分为一下几个部分

• 前言
• 介绍
• 代码
• 结果
• Points

前言

由于前段时间赶团队培训进度，后面需要对培训内容进行总结，因此以后相当一部分时间在 homework 上面的时间可能会减少，因此先贴出主要思路及要点，后面抽时间进行细节补充与整理

又挖坑了…QAQ

介绍

递归是一种在计算机科学和数学中广泛应用的概念和技术，通过不断直接或者间接调用自身函数，来解决一个规模比较大的问题，通过不断地将问题分解为规模更小的子问题，直到子问题简单到可以直接求解，最终将这些子问题的解组合起来得到原问题的解。

所以简单的递归函数一般由两部分组成：

1. 基本情况的返回值
2. 递归关系的表达式

例如对于求阶乘的函数：

int factorial (int n ) {
    // part 1
    if(n < 0) return 0;
    if(n == 1) return 1;
    
    // part 2
    return factorial(n)*factorial(n-1);
} // end of factorial

				

					
				
				

					
				
				

					
				
				

					
				
			

对应调用过程：

=> factorial(5)
=> 5 * factoria(4)
=> 5 * (4 * factoria(3))
=> 5 * (4 * (3 * factoria(2)))
=> 5 * (4 * (3 * (2 * factoria(1))))
=> 5 * (4 * (3 * (2 * 1)))
=> 5 * (4 * (3 * 2))
=> 5 * (4 * 6)
=> 5 * 24
=> 120

				

					
				
				

					
				
				

					
				
				

					
				
			

这里有一个在 python 学习中学到的点：

递归与尾递归优化：

递归函数由于每次 调用自身，所以存在一个函数压栈的问题，会增大程序的内存开销。

而尾递归思想则是利用一个新的变量存储每次递归处理后的数据，去除函数压榨问题，例如：

def factorial(n):
    return factorial_iter(n, 1)
 
def factorial_iter(num, product):
    if num == 1:
        return product
    return factorial_iter(num - 1, num * product)

				

					
				
				

					
				
				

					
				
				

					
				
			

对应 factorial (5) 调用如下：

=> factorial_iter(5, 1)
=> factorial_iter(4, 5)
=> factorial_iter(3, 20)
=> factorial_iter(2, 60)
=> factorial_iter(1, 120)
=> 120

				

					
				
				

					
				
				

					
				
				

					
				
			

代码

#include <stdio.h>
 
/**
 * Recursive addition.
 */
int addTo(int paraN) {
	int tempSum;
	printf("entering addTo(%d)\r\n", paraN);
	if (paraN <= 0) {
		printf(" return 0\r\n");
		return 0;
	} else {
		tempSum = addTo(paraN - 1) + paraN;
		printf(" return %d\r\n", tempSum);
		return tempSum;
	}// Of if
}// Of addTo
 
/**
 * A clear version.
 */
int clearAddTo(int paraN) {
	if (paraN <= 0) {
		return 0;
	} else {
		return clearAddTo(paraN - 1) + paraN;
	}// Of if
}// Of clearAddTo
 
/**
 * Test the addTo function.
 */
void addToTest() {
	int n, sum;
    printf("---- addToTest begins. ----\r\n");
 
	n = 5;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);
 
	n = 1;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);
 
	n = -1;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);
 
 
    printf("---- addToTest ends. ----\r\n");
}// Of addToTest
 
/**
 The entrance.
 */
void main() {
	addToTest();
}// Of main

				

					
				
				

					
				
				

					
				
				

					
				
			

结果

---- addToTest begins. ----
entering addTo(5)
entering addTo(4)
entering addTo(3)
entering addTo(2)
entering addTo(1)
entering addTo(0)
 return 0
 return 1
 return 3
 return 6
 return 10
 return 15
 
0 adds to 5 gets 15.
entering addTo(1)
entering addTo(0)
 return 0
 return 1
 
0 adds to 1 gets 1.
entering addTo(-1)
 return 0
 
0 adds to -1 gets 0.
---- addToTest ends. ----
Press any key to continue

				

					
				
				

					
				
				

					
				
				

					
				
			

总结 – 递归函数相关注意事项

如何写递归函数

首先需要观察程序是否具有可迭代性质

再研究此次迭代与上一个迭代是否具有联系

然后写出前后迭代的关系式子（也就是后面的递推关系式）

接着确定初始条件（一般是 a1 a2 的数值）

最后分块书写递推函数（终止条件 Part + 递推关系 Part）

递归函数的时空复杂度

空间复杂度一般是看最大调用次数

时间复杂度要么手算要么画成递归树，树的深度代表时间复杂度