什么是函数递归?
我觉得特别贴切“递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。
循环:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门(若前面两扇门都一样,那么这扇门和前两扇门也一样;如果第二扇门比第一扇门小,那么这扇门也比第二扇门小,你继续打开这扇门,一直这样继续下去直到打开所有的门。但是,入口处的人始终等不到你回去告诉他答案。”
再放一个通俗易懂的列子,帮助大家更好的理解递归:
我需要打开快递包装,于是买了个剪刀。但是剪刀也有包装,所以我又买了一个剪刀,这个剪刀上又有包装,所以我又买了个剪刀。。。
最后我没钱了,于是我用牙撕开了最后一个剪刀的包装,然后用这个剪刀打开了倒数第二个简单的包装,然后。。。最后用第一个剪刀打开了快递的包装,拿出了东西。
这个沙雕的过程就叫递归,递归必须要有停止条件(例子中是我把钱花完),要不然你就会拥有无数的剪刀,但又打不开快递(忘了目的系列)。
void print(unsigned int n) // n=1234
{if (n > 9){print(n / 10); //123 12 1}printf("%d ", n % 10); 1 2 3 4
}int main()
{unsigned int num = 0;scanf("%u", &num);print(num);return 0;
}
2.编写函数不允许创建临时变量,求字符串的长度。
int my_strlen(char* s)
{if (*s != '\0'){return 1 + my_strlen(s + 1);}else{return 0;}
}int main()
{char arr[10] = { "abcdaaaa" };int len = my_strlen(arr);printf("%d\n", len);return 0;
}
3.求n的阶乘。
int Fac(int n)
{if (n <= 1){return 1;}else{return n*Fac(n - 1);}
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fac(n);printf("%d\n", ret);return 0;
}
4.求斐波那契数列底n个数的值。
int Fib(int n)
{if (n <= 2)return 1;elsereturn Fib(n - 1) + Fib(n - 2);
}int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);return 0;
}
5.字符串逆序(递归实现)【将参数字符串中的字符反向排列,不是逆序打印。】
思路:
逆置字符串,循环的方式实现非常简单
1. 给两个指针,left放在字符串左侧,right放在最后一个有效字符位置
2. 交换两个指针位置上的字符
3. left指针往后走,right指针往前走,只要两个指针没有相遇,继续2,两个指针相遇后,逆置结束
#include <stdio.h>
void reverse_string(char* arr)
{int len = strlen(arr);char tmp = *arr;*arr = *(arr + len - 1);*(arr + len - 1) = '\0';if (strlen(arr+1)>=2)reverse_string(arr + 1);*(arr + len - 1) = tmp;
}
/*或者不用指针表示:
int my_string(char* str)
{int count = 0;while (*str != '\0'){count++;str++;}return count;
}void reverse_string(char str[])
{int len = my_string(str);int tmp = str[0];str[0] = str[len - 1];str[len - 1] = '\0';if (my_string(str + 1) >= 2){reverse_string(str + 1);}str[len - 1] = tmp;
}
*/
int main()
{char arr[] = { "abc" };reverse_string(arr);printf("%s", arr);
}
6.计算一个数的每位之和(递归实现)
#include <stdio.h>
int DigitSum(int n)
{if (n > 9){return DigitSum(n / 10) + n % 10;}elsereturn n;
}int main()
{int n = 0;scanf("%d", &n);int ret = DigitSum(n);printf("%d\n", ret);
}
7.递归实现n的k次方
#include <stdio.h>
int pow(int n, int k)
{if (k == 0)return 1;else if (k >= 1)return n*pow(n, k - 1);
}
int main()
{int n = 0;int k = 0;scanf("%d %d", &n, &k);int ret = pow(n, k);printf("%d\n", ret);return 0;
}
8. 求 1+2+3....+n 的值 。
#include <stdio.h>
int sum(int n)
{if (n == 1)return 1; // 出口 (必要的)elsereturn (sum(n - 1) + n); //根据表达式 F(n)=f(n-1)+n 取等号后边式子 称为 递推关系式
}
int main()
{int n = 0;scanf("%d", &n);int ret = sum(n);printf("%d\n", ret);/*int num = sum(100);printf("%d\n", num);*/return 0;
}
9. 已知一个整形数组,求出前n项数字之和。
#include <stdio.h>
int sum(int arr[], int n)
{if (n == 0)return arr[0];elsereturn sum(arr, n - 1) + arr[n];
}
int main()
{int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int ret = sum(arr, 4);printf("%d\n", ret);return 0;
}
10. 求一个已知数组里面前n个数字里面的最大值 (下标为n计算)
#include <stdio.h>
int max(int arr[], int n)
{if (n == 0)return arr[0];else if (max(arr, n - 1) > arr[n])return max(arr, n - 1);elsereturn arr[n];
}
int main()
{int arr[] = { 7, 4, 8, 6, 3, 2, 9, 11, 5 };int n = 0;scanf("%d", &n);int ret = max(arr, n);printf("%d\n", ret);return 0;
}
11. 递归中的冒泡排序
void bubble(int arr[], int L, int R)
{if (L < R){int i = 0;for (i = L; i <= R - 1; i++){if (arr[i] > arr[i + 1]){int tmp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = tmp;}}bubble(arr, L, R - 1);}
}
int main()
{int i = 0;int arr[7] = { 7, 6, 5, 4, 3, 2, 1 };bubble(arr, 0, 6);for (i = 0; i < 7; i++){printf("%d ", arr[i]);}return 0;
}
12.求两数最大公约数
int gcd(int a, int b)
{if (a%b == 0)return b;else{int r = 0;r = a%b;return gcd(b, r);}
}
int main()
{int a = 0;int b = 0;scanf("%d %d", &a, &b);int ret = gcd(a, b);printf("%d\n", ret);
}
总结:
什么时候用递归:
1.当解决一个问题递归和非递归都可以使用,且没有明显问题。那就可以使用递归。
2.当解决一个问题递归写起来很简单,非递归比较复杂,且递归没有明显问题,那就用递归。3.如果说用递归解决问题,写起来简单,但是有明显问题,那就不能使用递归。得写出非递归的方式来解决。
小tips :
递归想的深入了,很容易被绕进去,这时我们就要记住“ 我们是懒懒的老和尚,计算机就是忙碌的小和尚,我们不要管他们。” 把它想成,在还没有到达递归函数出口位置时,在做重复的事情就可以了。既然是重复的事情就没有必要每一样都去验证了 。