【练习10】
Ackerman函数的递归实现与迭代实现。Ackerman(4,1)以上都无法计算出来。
原文地址：http://blog.csdn.net/pku_zzy/article/details/51933791
1、递归实现
int ack(int m,int n) { if (m==0) return n+1; else if (n==0) return ack(m-1,1); else return ack(m-1,ack(m,n-1)); }
2、迭代实现
int Ack(int M,int N) { int top=0,m,n; int stack[10000][4]={{M,N}};//记录信息m,n,Ack(m,n),跳转出口种类; while (true) { m=stack[top][0]; n=stack[top][1]; if (m==0) stack[top][2]=n+1; else if (n==0) { top++; stack[top][0]=m-1; stack[top][1]=1; stack[top][3]=1; continue; l1: stack[top][2]=stack[top+1][2]; } else { top++; stack[top][0]=m-1; top++; stack[top][0]=m; stack[top][1]=n-1; stack[top][3]=2; continue; l2: stack[top][1]=stack[top+1][2]; stack[top][3]=3; continue; l3: stack[top][2]=stack[top+1][2]; } if (top==0) break; top--; switch (stack[top+1][3]) { case 1:goto l1; case 2:goto l2; case 3:goto l3; } } return stack[0][2]; }
【练习11】汉诺塔递归问题 Hanoi Recursion
函数的参数：移动盘子的个数，从哪个柱子移动到哪个柱子，以哪个柱子为辅助，共计4个参数。
一般递归程序转换为循环的步骤： （1）递归函数主体的转换：转换为循环，while(1)即可；
（2）递归调用的转换：将当前参数、局部变量…（活动记录）压栈；参照调用方式改变参数，继续循环；
（3）函数执行结束——递归返回的处理：若栈空，整个递归过程结束，跳出循环；否则，将调用者的活动记录弹出栈，恢复其环境，继续循环；
（4）递归函数不同入口的区分——返回地址的处理：上例：ENTRANCE、FIRST、SECOND，活动记录的一部分，与参数、局部变量一同压栈、出栈，在循环主体中，根据当前活动记录的入口值，执行不同代码
具体递归代码可参见：http://blog.csdn.net/kkkkkxiaofei/article/details/8333644/
【练习12】递归求解powerset(S)，即S集合的所有子集。
http://www.mhhe.com/engcs/compsci/sahni/c1/E5.HTM
http://bbs.csdn.net/topics/380062729
S是集合，Sn是子集，SA是可选子集，Ps是幂集。 解：算法Powerset(SN,SA,PS)// S是集合，SN是子集，SA是可选子集，PS是幂集 Powerset 1[递归出口] If SA={ } then {PS<—PS+SN. Return.} Powerset 2[把SN加入PS] PS<—PS+SN Powerset 3[递归调用] FOR （ 所有 Item 属于SA） DO {Powerset(SN 并{Item}, SA<—SA-{item},PS)} Return.
下面这个算法，也是把集合做了一个0-1设置，从0~2^n逐个打印
#include <stdio.h> #include <string.h> #include <assert.h> /* 猜测结果 */ void print_sub_set(const char *set_str) { //assert(set_str);// 集合是否存在 const size_t LEN = strlen(set_str); const size_t PEAK = 0x1 << LEN;// 上限值 size_t i, j; assert(LEN < sizeof(size_t) * 8);// 集合是否过大 for (i = 0; i < PEAK; ++i) { for (j = 0; j < LEN; ++j) { if ((i >> j) & 0x1) { printf("%c", set_str[j]); } } printf("\n"); } } /* 测试代码 */ int main() { print_sub_set("ABCDE"); return 0; }
