New Code day16

1. 递归和非递归分别实现求第n个斐波那契数。 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
~递归形式
int fib(int n)
{
	if(n<3)
		return 1;
	return fib(n-1)+fib(n-2);
}
int main()
{
	int num = 0;
	scanf("%d",&num);
	printf("%d",fib(num));
	return 0;
}

~非递归形式
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//1. 递归和非递归分别实现求第n个斐波那契数。
int fib(int n)
{
	int i = 1;
	int a = 1;
	int b = 1;
	int c = 1;
	for(i=0; i<n-2; i++)
	{
		c = a+b;
		a = b;
		b = c;
	}
	return c;
}
int main()
{
	//非递归
	int num = 0;
	scanf("%d",&num);
	printf("%d",fib(num));
	return 0;
}

2. 编写一个函数实现n^k，使用递归实现 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//编写一个函数实现n^k，使用递归实现 
int power(int n,int k)
{
	if(k < 2)
		return n;
	return n*power(n,k-1);
}
int main()
{
	int sum = 0;
	int n = 0;
	int k = 0;
	scanf("%d %d",&n,&k);
	sum = power(n,k);
	printf("%d",sum);
	return 0;
}

3. 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和，例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和，
//例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19 
int DigitSum(int n)
{
	if(n <10)
		return n;
	return (n%10)+DigitSum(n/10);
}
int main()
{
	int sum = 0;
	int n = 0;
	scanf("%d",&n);
	sum = DigitSum(n);
	printf("%d",sum);
	return 0;
}

4. 编写一个函数reverse_string(char * string)（递归实现） 
实现：将参数字符串中的字符反向排列。 
要求：不能使用C函数库中 
的字符串操作函数。 

//普通版本
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
void reverse_string(char * arr)
{
	int left = 0;
	int right = strlen(arr)-1;
	int tmp = 0;
	while(left<right)
	{
		tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
int main()
{
	char arr[] = "hello bit";
	printf("%s\n",arr);
	reverse_string(arr);
	printf("%s\n",arr);
	return 0;
}

//正确版本~递归版（较普通版困难）
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
//编写一个函数reverse_string(char * string)（递归实现） 
//实现：将参数字符串中的字符反向排列。 
//要求：不能使用C函数库中的字符串操作函数。
void reverse_string(char * str)
{
	int len = strlen(str);
	char tmp = *str;
	*str = *(str+len-1);	
	*(str+len-1) = '\0';
	if(strlen(str)+1 > 1)
		reverse_string(str+1);
	*(str+len-1) = tmp;
}
int main()
{
	char arr[] = "hello bit";
	printf("%s\n",arr);
	reverse_string(arr);
	printf("%s\n",arr);
	return 0;
}

//此版本仅为倒序打印该字符串
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//编写一个函数reverse_string(char * string)（递归实现） 
//实现：将参数字符串中的字符反向排列。 
//要求：不能使用C函数库中的字符串操作函数。
void reverse_string(char * string)
{
	if(*string)
	{
        reverse_string(string+1);
		putchar(*string);
	}
}
int main()
{
	char arr[] = "hello bit yo";
	reverse_string(arr);
	printf("\n");
	return 0;
}

5. 递归和非递归分别实现strlen 

//递归
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
//递归和非递归分别实现strlen
int my_strlen(char * str)
{
	assert(str != NULL);
	if(*str == '\0')
		return 0;
	else
		return 1+my_strlen(str+1);
}
int main()
{
	char arr[] = "abcdef";
	printf("%d",my_strlen(arr));
	printf("\n");
	return 0;
}

//非递归
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
//递归和非递归分别实现strlen
int my_strlen(char * str)
{
	int tmp = 0;
	assert(str != NULL);	
	while(*str)
	{
		tmp++;
		str++;
	}
	return tmp;
}
int main()
{
	char arr[] = "abcdefeee";
	printf("%d",my_strlen(arr));
	printf("\n");
	return 0;
}

6. 递归和非递归分别实现求n的阶乘 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
//递归和非递归分别实现求n的阶乘 
int fac(int n)
{
	//递归
	if(n<2)
		return 1;
	return n*fac(n-1);
}
int main()
{
	int num = 0;
	scanf("%d",&num);
	printf("%d",fac(num));
	printf("\n");
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
//递归和非递归分别实现求n的阶乘 
int fac(int n)
{
	//非递归
	int tmp = n;
	while(tmp>1)
	{
		n = n*(tmp-1);
		tmp--;
	}
	return n;
}
int main()
{
	int num = 0;
	scanf("%d",&num);
	printf("%d",fac(num));
	printf("\n");
	return 0;
}

7. 递归方式实现打印一个整数的每一位

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
//递归和非递归分别实现求n的阶乘 
void print(int n)
{
	//递归
	if(n<10)
		printf("%d ",n);
	else
	{
		print(n/10);
		printf("%d ",n%10);		
	}

}
int main()
{
	int num = 0;
	scanf("%d",&num);
	print(num);
	printf("\n");
	return 0;
}