上海市崇明县建设中学网站,百度官方网站怎么做,七牛直播网站怎么做,建个站的网站打不开目录
1. 什么是递归#xff1f;
2. 函数递归的必要条件
2.1 接收一个整型值#xff08;无符号#xff09;#xff0c;按照顺序打印它的每一位。
代码如下#xff1a;
2.2 编写一个函数#xff0c;不用临时变量求字符串长度
代码如下#xff1a;
2.3 递归与迭代
…目录
1. 什么是递归
2. 函数递归的必要条件
2.1 接收一个整型值无符号按照顺序打印它的每一位。
代码如下
2.2 编写一个函数不用临时变量求字符串长度
代码如下
2.3 递归与迭代
2.3.1 求n!不考虑溢出
代码如下
2.3.2 求第n个斐波那契数不考虑溢出
代码如下 1. 什么是递归 程序调用自身的编程技巧称为i而递归recursion。递归作为一种算法再程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为为一个与原问题相似的规模较小的问题来求解递归策略只需要只需要少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。递归的主要思考方式在于大事化小现在看这个概念可能有一点抽象我们举一个最简单的例子 int main()
{printf(LOVE YOU\n);main();//函数在里面自己调用自己就是递归return 0;
} 但是这个代码还是有一定的问题的它会栈溢出。 内存分为栈区、堆区和静态区我们知道当我们调用函数时它会在栈区申请空间。但是我们这个函数是无限循环的它一直调用main函数直到栈区没有空间了它才停止。 当然这只是一个例子我们在写代码的时候不会这样写。 2. 函数递归的必要条件 存在限制条件当满足这个限制条件的时候递归便不再继续。每次递归调用之后越来越接近这个限制条件。2.1 接收一个整型值无符号按照顺序打印它的每一位。 例如 输入1234输出1 2 3 4. 我们可以先看看能不能计算 1234%104打印 1234/10123 123%103打印 123/1012 12%102打印 12/101 1%101打印 这样虽然可以计算但是顺序错了用刚刚学的递归就可以解决我们这里的限制条件是只剩下个位数后不需要递归 代码如下 #include stdio.hvoid Print(unsigned int n)
{if (n 9){Print(n / 10);}printf(%d , n % 10);
}int main()
{unsigned int num 0;scanf(%u, num);Print(num);return 0;
} 代码可能有些难理解我们看下面的图 递归的递是递推就是上面的绿色箭头 递归的归是回归就是上面的红色箭头 2.2 编写一个函数不用临时变量求字符串长度
乍一看这个问题好像很难没关系我们先减小难度。编写一个函数求字符串长度。 很简单对吧我们再加一点难度用调用函数写。 arr[10]a b c d e f \0 _ _ _ 首先我们要知道数组 arr 的指针就是第一个字母 a 的指针当我们的指针 str 指向 a 时我们记为 1 然后 str指针向下走指向 b ……最后当 str \0 时停止计数所以这是一个循环。定义一个计数变量 count 每当进入循环 countstr当循环结束返回 count 。#include stdio.h
#include string.hint my_strlen(char* str)
{int count 0;while (*str ! \0){count;str;}return count;
}int main()
{char arr[10] abcdef;int len my_strlen(arr);printf(%d\n, len);return 0;
}
理解之后我们进一步改良使其符合题目 题目不需要临时变量count就不能用了。但是我们还是之前的思路只是用递归的方法 首先递归要有一个限制条件指针不为 \0 。满足这个条件后指针1但是我们还要计数直接返回的时候1。否则也就是说如果一开始就是 \0 那我们就直接返回0。 代码如下
#include stdio.h
#include string.hint my_strlen(char* str)
{if (*str ! \0){return 1 my_strlen(str 1);}elsereturn 0;
}int main()
{char arr[10] abcdef;int len my_strlen(arr);printf(%d\n, len);return 0;
}
2.3 递归与迭代 循环是迭代的一种 循环(loop),指的是在满足条件的情况下,重复执行同一段代码。比如,while语句。 循环则技能对应集合,列表,数组等,也能对执行代码进行操作。迭代(iterate),指的是按照某种顺序逐个访问列表中的每一项。比如,for语句。 迭代只能对应集合,列表,数组等。不能对执行代码进行迭代。2.3.1 求n!不考虑溢出 我们以前也写过求 n! 主函数输入n定义ret接收调用函数 fac 的返回值打印 ret 。调用函数定义 i1 和 ret1 循环出 1 - n 的数让 i n 不断让 ret ret * i 。#include stdio.hint fac(int n)
{int i 0;int ret 1;for (i 1; i n; i){ret ret * i;}return ret;
}int main()
{int n 0;scanf(%d\n, n);int retfac(n);printf(%d\n, ret);return 0;
} 除了这种循环迭代的写法我们还可以改良一下用递归写fac(n) n * fac(n-1) 当 n 1 时返回1当 n 1 时返回 n * fac(n-1)代码如下 int fac(int n)
{if (n 1)return 1;elsereturn n * fac(n - 1);}int main()
{int n 0;scanf(%d, n);int ret fac(n);printf(%d, ret);return 0;
}
2.3.2 求第n个斐波那契数不考虑溢出 斐波那契数列指的是这样一个数列1123581321345589... 这个数列从第3项开始每一项都等于前两项之和。在数学上斐波那契数列以如下被以递推的方法定义F(0)0F(1)1, F(n)F(n - 1)F(n - 2)n ≥ 2n ∈ N*要写这个函数首先我们要知道前两个数字第三项开始就是前两项之和我们只需要计算到 n * (n-1) 。 当 n 2 斐波那契数是 1 当 n 2 斐波那契数是前两项之和 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, ret);return 0;
} 虽然这种方法可行但是过程非常繁琐当你输入的数字较大时需要递归很多次有很多重复大量的计算。 递归虽然可行但是有没有其他的更简单的方法不用递归直接从前往后算前两个相加等于第三个用迭代的方式计算 代码如下 int Fib(int n)
{int a 1;int b 1;int c 1;while (n3){c a b;a b;b c;n--;}return c;
}
int main()
{int n 0;scanf(%d, n);int ret Fib(n);printf(%d, ret);return 0;
}
