#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
//-------------------------------------------------------------------------------------------第九次作业 函数递归等
//-------------------------------------------------------------------------------单选1
关于递归的描述错误的是:(C)
A.存在限制条件,当满足这个限制条件的时候,递归便不再继续
B.每次递归调用之后越来越接近这个限制条件
C.递归可以无限递归下去
D.递归层次太深,会出现栈溢出现象
//-------------------------------------------------------------------------------单选2
根据下面递归函数:调用函数Fun(2),返回值是多少(D)
int Fun(int n)
{if(n == 5)return 2;elsereturn 2*Fun(n+1);
}A.2
B.4
C.8
D.16
*///-------------------------------------------------------------------------------编程题3：打印整数每一位
//递归方式实现打印整数的每一位 例如 1234 打印 1 2 3 4
//123 4
//12 34
//1 2 3 4
void Print(unsigned int n) //1234
{if (n > 9){Print(n / 10);}printf("%d ", n%10);
}int main()
{unsigned int num = 0;scanf("%u", &num); // 1234Print(num);return 0;
}//-------------------------------------------------------------------------------编程题4：求 n 的阶乘
//递归和非递归，分别实现求n的阶乘（不考虑溢出问题）
//-----------------------------------------------------------------4.1 循环求阶乘n
int main()
{int n = 0;scanf("%d", &n);int i = 0;int num = 1;for (i = 1; i <= n; i++){num = num * i;}printf("%d\n", num);return 0;
}//-----------------------------------------------------------------4.2 递归求阶乘n
//5!=1*2*3*4*5
//5!=4!*5
//4!=3!*4
//3!=2!*3
//2!=1!*2
//1!=1
int factorial(int n) //5
{if (n > 0)return factorial(n - 1) * n;elsereturn 1;
}int main()
{int n = 0;scanf("%d", &n);int ret = factorial(n);printf("%d\n", ret);return 0;
}//-------------------------------------------------------------------------------编程题5：strlen的模拟
//递归和非递归分别实现strlen
//----------------------------------------------------------------5.1 循环求strlen
int my_strlen(char arr[])
{int i = 0;int count = 0;while (arr[i] != '\0'){count++;i++;}return count;
}int main()
{char arr[] = "abcdef"; // [a b c \0]int len = my_strlen(arr); // 函数传参时，传的是首字符 a 的地址printf("%d\n", len);return 0;
}//-----------------------------------------------------------------5.2 递归求strlen
//my_strlen("abc");
//1+my_strlen("bc");
//1+1+my_strlen("c");
//1+1+1+my_strlen("\0");
//1+1+1+0
int my_strlen(char* arr)
{if (*arr != '\0')return 1 + my_strlen(arr + 1);elsereturn 0;
}int main()
{char arr[] = "abcdefgh"; // [a b c d e f g h\0]int len = my_strlen(arr); // 函数传参时，传的是首字符 a 的地址printf("%d\n", len);return 0;
}//-------------------------------------------------------------------------------编程题6：字符串逆序（递归实现）
//编写一个字符串 reverse_string(char* string)
//将参数字符串中的字符反向排列，不是逆序打印
//不能使用V函数库中的字符串操作符
// 例如： char arr[]="abcdef";
// 逆序之后数组里的内容变成 fedcba//--------------------------------------------------------------6.1 用循环求逆序
int main()
{char arr[] = "abcdef";int sz = sizeof(arr) / sizeof(arr[0]); //把 \0 也计算进去了，算出来7/1=7int left = 0;int right = sz - 2; //所以 sz-2// int right=strlen(arr)-1; //用strlen 求字符串长度 6while (left < right){char tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;left++;right--;}printf("%s\n", arr);return;
}//---------------------------------------------------------------6.2 用函数求逆序
void reverse(char arr[])
{int left = 0;int right = strlen(arr) - 1; //用strlen 求字符串长度 6while (left < right){char tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;left++;right--;}
}int main()
{char arr[] = "abcdef";reverse(arr);printf("%s\n", arr);return;
}//------------------------------------------------------------------6.3 用递归求逆序
int my_strlen(char* str)
{int count=0;while (*str != '\0'){count++;str++;}return count;
}void reverse(char* str)
{char tmp = *str; //1int len = my_strlen(str);// 不用库函数，自己定义一个函数*str = *(str + len - 1); //2*(str + len - 1) = '\0'; //3if(strlen(str+1)>=2) //(递归的条件)reverse(str + 1); //4*(str + len - 1) = tmp; //5
}int main()
{char arr[] = "abcdef";reverse(arr);printf("%s\n", arr);return;
}//------------------------------------------------------------------6.4 用递归求逆序plus
int my_strlen(char* str)
{int count=0;while (*str != '\0'){count++;str++;}return count;
}void reverse(char arr[], int left, int right)
{if(left<right)//-------------------必须加这个条件{char tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;if (left < right)reverse(arr, left + 1, right - 1);}}int main()
{char arr[] = "abcdefg";int left = 0;int right = my_strlen(arr) - 1;reverse(arr,left,right);printf("%s\n", arr);return 0;;
}//---------------------------------------------------------------------------------编程题7：计算一个数的每位之和
//写一个递归函数 DigitSum(n)，输入一个非负整数，返回组成他的非负之和
//例如：调用 DigitSum(1729)，应该返回1 7 2 9，和是19
//输入 1279 输出19
int DigitSum(unsigned int n) //1729
{if (n > 0)return DigitSum(n / 10) + n % 10;elsereturn n;
}int main()
{unsigned int n = 0;scanf("%d", &n);int ret = DigitSum(n);printf("%d\n", ret);return 0;
}//-------------------------------------------------------------------------------编程题8：递归实现n的k次方
//编写一个函数实现 n 的k次方
double Power(int n, int k)
{if (k > 0)return n * Power(n, k - 1);else if (k == 0)return 1;elsereturn 1.0 / Power(n, -k);}int main()
{int n = 0;int k = 0;scanf("%d %d", &n, &k);double ret = Power(n, k);printf("%lf\n", ret);return 0;
}//-------------------------------------------------------------------------------编程题9：计算斐波那契数
//递归和非递归分别实现求第n 个斐波那契数
//求第 n 个斐波那契数（不考虑溢出）
// 1 1 2 3 5 8 13 21 34 55...
// 前两数相加等于第三个数
int Fibonacci(int n)
{if (n < 3)return 1;if (n >= 3){return Fibonacci(n - 1) + Fibonacci(n - 2);}}int main()
{int n = 0;scanf("%d", &n);int ret = Fibonacci(n);printf("%d\n", ret);return 0;
}
