递归是指将一个很大的问题转化成同样形式但小一些的问题加以解决。“同样形式”是这个定义的关键，如果没有这个定语，这个定义就和逐步精化一样了。递归的特别之处在于递归分解中的子问题和原有问题有相同的形式。
阶乘函数，在数学中表示为n!，表示为1到n之间的所有整数的连乘积。
1
2
3
4
5
6
7
8
int Fact(int n){
if(n==0){
return 1;
}
else{
return n * Fact(n-1);
}
}
1
2
3
4
5
6
7
8
9
10
int Fact(int n){
int i, product;
if(n==0){
return 1;
}
for(i=1, product=1; i<=n; i++){
product *= i;
}
return product;
}
费波那契问题是，如果它们按照如下规则，兔子的数量是如何从一代到一代的增长：
如果在1月引入一对未发育成熟的兔子，那么在年终时将会有多少对兔子？
1
2
3
4
5
6
7
8
int Fib(int n){
if(n < 2){
return n;
}
else{
return Fib(n-1) + Fib(n-2);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int Fib(int n){
return AdditiveSequence(n, 0, 1);
}
int AdditiveSequence(int n, int t0, int t1){
if(n == 0){
return t0;
}
if(n == 1){
return t1;
}
return AdditiveSequence(n-1, t1, t0+t1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Fib(int n){
int t0 = 0,
t1 = 1,
tn, i;
if(n == 0){
return t0;
}
if(n == 1){
return t1;
}
for(i=1; i<n; i++){
tn = t0 + t1;
t0 = t1;
t1 = tn;
}
return tn;
}
回文是一种字符串，它的正向读和反向读都是一样的。比如“level”和“noon”。由于任何一个字符长度大于1的回文，必须在其内部包含一个更短的回文，所以检测一个字符串是否为回文，需要：
很明显，任何一个只有一个字符组成的字符串是一个回文，空字符串也可以将其看做回文。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef enum {false, true} bool;
typedef char *string;
bool IsPalindrome(string str){
int len = strlen(str);
if(len <= 1){
return true;
}
else{
bool result1 = str[0] == str[len-1];
if(result1){
string sub = malloc(len-1);
strncpy(sub, str+1, len-2);
sub[len-2] = '\0';
bool result2 = IsPalindrome(sub);
free(sub);
return result1 && result2;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef enum {false, true} bool;
typedef char *string;
bool IsPalindrome(string str){
return CheckPalindrome(str, strlen(str));
}
static bool CheckPalindrome(string str, int len){
if(len <= 1){
return true;
}
else{
return str[0]==str[len-1] && CheckPalindrome(str+1, len-2);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef enum {false, true} bool;
typedef char *string;
bool IsPalindrome(string str){
int i;
int len = strlen(str);
int middle = len/2;
for(i=0; i<middle; i++){
if(str[i] != str[len-1-i]){
return false;
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef enum {false, true} bool;
typedef char *string;
int FindStringInSortedArray(string key, string array[], int n){
return BinarySearch(key, array, 0, n-1);
}
static int BinarySearch(string key, string array[], int low, int high){
int mid, cmp;
if(low > high){
return -1;
}
mid = (low + high) / 2;
cmp = strcmp(key, array[mid]);
if(cmp == 0){
return mid;
}
else if(cmp < 0){
return BinarySearch(key, array, low, mid-1);
}
else{
return BinarySearch(key, array, mid+1, high);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef enum {false, true} bool;
bool IsEven(unsigned n){
if(n == 0){
return true;
}
else{
return IsOdd(n-1);
}
}
bool IsOdd(unsigned n){
return !IsEven(n);
}
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void MoveSingleDisk(char start, char finish){
printf("%c - %c\n", start, finish);
}
void MoveTower(int n, char start, char finish, char temp){
if(n==1){
MoveSingleDisk(start, finish);
}
else{
MoveTower(n-1, start, temp, finish);
MoveSingleDisk(start, finish);
MoveTower(n-1, temp, finish, start);
}
}
生成一组特定字母各种可能的排列组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static void ListPermutations(string str){
RecursivePermute(str, 0);
}
static void RecursivePermute(string str, int k){
int i, len;
len = strlen(str);
if(len == k){
printf("%s\n", str);
}
else{
for(i=k; i<len; i++){
ExchangeCharacters(str, k, i);
RecursivePermute(str, k+1);
ExchangeCharacters(str, k, i);
}
}
}
static void ExchangeCharacters(string str, int p1, int p2){
if(p1 != p2){
str[p1] ^= str[p2];
str[p2] ^= str[p1];
str[p1] ^= str[p2];
}
}