数据结构什锦（一）——绪论、递归与回溯.md

关于我自己阅读《数据结构与算法经典问题解析》的一点小笔记与想法。不定时更新，不保证能完结~ε≡٩(๑>₃<)۶

绪论

粗略浏览了一下绪论部分，主要介绍了如何计算算法的时间复杂度。涉及到比较多的数学计算，这里暂且先按下不表，还是多看书上的例题自己总结来得快吧。

递归和回溯

递归

函数自己调用自己，我们称之为递归。递归让函数得以通过调用自身的一个小副本来求解小问题的方法去解决大问题。

比较经典的利用递归去解决的问题：

裴波那契数列，数的阶乘
合并排序，快速排序
二分搜索
树的遍历
图的遍历
动态规划
分治算法
汉诺塔问题
回溯算法

递归的格式

一般来说，函数会遇到一个不需要调动自身就可以解决的子问题，我们称之为基本情况，与之相对的，一个需要调动自己来解决的问题，我们称之为递归情况。我们可以参考以下格式来编写递归函数。

if (是基本情况吗)
    直接求解，并返回结果
else if (是另一种基本情况吗)
    直接求解，并返回结果
else //即递归情况
    返回（进行某些处理步骤，然后是针对更小规模问题的函数调用）

比如我们现在用C语言去实现一个计算数的阶乘的递归函数，函数编写如下：

int Fact(int n)
{
    if (n==1)
        return 1;
    else if (n==0)
        return 1;
    else
        return n*Fact(n-1)
}

递归与迭代

我们一般总会面临一个选择，是使用递归好还是迭代更好。一般来说，迭代使一个问题变得简单，但是它会产生额外的开销（使用了大量的系统栈中的空间）

一般来说递归的特点如下：

当到达基本情况时，递归终止
每次调用递归会占用内存空间
如果递归无法终止，会造成内存耗尽或系统栈溢出
运用递归的方法更加容易求解一些问题

而迭代的特点如下：

当迭代的证明不成立时，迭代终止
每次迭代不需要额外空间，因为使用的是同一片形参，只需要更新储存的值就好
因为循环过程不会产生额外的内存开销，所以无限循环可以无限的进行下去
一个问题的迭代方案可能不一定有递归方案那么显而易见

回溯

回溯法是一种利用分治算法的穷举搜索方法。

有时解决问题的最好算法是尝试所有的可能性
有时候这种算法的效率并不高，但有一些工具来改善这些算法
回溯法通过剪枝技术加快穷举搜索的速度

应用回溯法算法举例如下：

二进制串：生成所有的二进制串
生成k进制串
背包问题
广义字符串
图着色问题

这里放一道例题，要求生成所有长度为k的字符串，并且应用了回溯算法。

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>

char* A;
int count = 0;

void Binary(int n)
{
	if (n < 1)
	{
		printf("%s\n", A);
		count++;
	}
	else
	{
		A[n - 1] = '0';
		Binary(n - 1);
		A[n - 1] = '1';
		Binary(n - 1);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);
	A = malloc(n * sizeof(char));
	A[n] = '\0';

	Binary(n);
	printf("%d", count);

	return 0;
}