一些递归算法的实现

要求将一个自然数拆分成不同的组合如下是7的拆分：

16

115

1114

11113

111112

1111111

11122

1123

124

1222

133

25

223

34

使用递归的思想，用一个数组存放已经拆分出来的结果，拆分的时候为了避免重复，拆分数由小至大，假设拆分至a[i]，a[i]能否拆分取决于a[i]/2是否大于a[i-1]，否则拆分结束。

#include <stdio.h>

void split(int t, int * a) 

{

int j = t, L = a[t];

for(int k = 0; k <= t; ++k)

printf("%d", a[k]);

printf("\n");

for(int i = a[j - 1]; i <= L/2; ++i) 

{

a[j] = i; 

a[j + 1] = L - i;

split(j + 1,a);

}

}

void splitNum(int n, int * a) 

{

for(int i = 1; i <= n/2; ++i) 

{

a[0] = i;

a[1] = n - i;

split(1,a);

}

}

n个元素的全排列：

void permutation(int *a, int size, int cur) 

{

if(cur == size - 1)

{

for(int j = 0; j < size; ++j)

printf("%d ",a[j]);

printf("\n");

}

else {

for(int i = cur; i < size; ++i)//后面元素依次有cur交换

{

int temp = a[cur];

a[cur] = a[i];

a[i] = temp;

permutation(a, size, ++cur);//递归

--cur;

temp = a[cur];

a[cur] = a[i];

a[i] = temp;

}

}

}

汉诺塔问题：

void hanoi(int n,char x, char y, char z)

{

if(1 == n) 

{

printf("%d %c -> %c \n", n, x, z);

}

else {

hanoi(n - 1, x, z, y);

printf("%d %c -> %c\n", n, x, z);

hanoi(n - 1, y, x, z);

}

}