递归案例

阳光穿透心脏的1/2处 2022-05-14 15:11 286阅读 0赞

递归的难点就在于递归深入点的设计，以及其中逻辑公式的提取。

### 一.字符串逆置 ###

方法一：定义一个全局变量作为数组下标。

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    char dst[32];
    static int i = 0;
    void reverse_show(char *str)
    {
    	if (*str == 0)
    		return;
    
    	reverse_show(str + 1);
    	dst[i++] = *str;
    }
    
    int main(int argc, char *argv[])
    {
    	char str[32] = "hello world";
    	reverse_show(str);
    	printf("%s\n", dst);
    
    	system("pause");
    	return 0;
    }

方法二：使用字符串拷贝函数，将递归回退的\*str拷贝到dst中，实现了逆序。

void reverse_show(char *str)
    {
    	if (*str == 0)
    		return;
    
    	reverse_show(str + 1);
    	dst[i++] = *str;
    
    	//使用字符串拷贝函数，将递归回退的*str拷贝到dst中，实现了逆序。
    	strncat(dst, str, 1);
    }

### 二.阶乘 ###

逻辑公式：0!=1,n!= (n-1)!\*n

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

### 三.斐波那契数列 ###

F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N\*）

int fun(int n)
    {
    	if (n == 2 || n == 1)
    		return 1;
    
    	return fun(n - 1) + fun(n - 2);
    
    }

### 四.倒序输出正整数 ###

与上面逆序输出字符串的方法不同，字符串使用的是++操作，其本身就是正序的，所以要先深入，后输出；而对数值使用的是取余操作，得到的是倒序的，所以先输出，后取余。

void fun(int n)
    {
    	printf("%d", n % 10);//输出最后一位
    	if (n >= 10)
    		fun(n / 10);//抹掉最后一位
    }

### 五.汉诺塔 ###

fun(n) = 2\*fun(n-1)+1;

解法一：

int fun(int n) {
    	if (n == 1) return 1;
    	return 2 * fun(n - 1) + 1;
    }

解法二：

static int b = 0;
    void hanoi_next(int n) {
    	if (n > 0) {//在此处检测0，所以要把计数器写在里面。
    		hanoi_next(n - 1);
    		b++;
    		hanoi_next(n - 1);
    	}
    }