-
递归函数
2017-08-11 11:00:12递归函数纠结了2天的递归函数,记录一下
<php> function sum($n,$m){ if($m<=$n){ return $n; } return sum($n,$m-1)+$m; } echo sum(1,3); // => 6 </php>
推算一下运算过程
sum(1,3) = sum(1,2) + 3 , sum(1,2) = sum(1,1) + 2 , sum(1,1) =1
得到了sum(1,1) =1 后,再进行倒推
sum(1,1) =1 , sum(1,2) = 1 + 2 = 3 , sum(1,3) = 3+3=6
-
C语言递归函数C语言递归函数C语言递归函数
2015-11-09 23:42:15//用递归函数来计算N的阶乘 double factorial(int n) { double result; if(n) { printf("输入错误\n"); } else if(n==1 ||n==0) { result=1; } else { result=factorial(n-1)*n; //n=5 5-1=4 4*5... -
递归函数
2007-03-07 21:16:00递归函数 [ firedy 发表于 2007-1-20 12:54:00 ]递归函数 [ firedy 发表于 2007-1-20 12:54:00 ]学C数据结构时在讲栈的章节里重点提到递归函数的思想,现在我在看java时同样遇到递归的思想,所以就想整理整理一下自己的“笔记”,理一下自己的思路。
递归的定义:递归是指在定义自身的同时又出现了对自身的调用。 如果一个函数在其定义体内直接调用自己,则称其为直接递归函数; 如果一个函数经过一系列的中间调用语句,通过其它函数间接调用自己,则称其为间接递归函数。 见名思意,递归实际上是递推与回归的结合。
下面见一个例子,这个例子很有意思,因为在我考数据结构时且好出了这道题,我刚好在考试前复习时见道同样的题,然后我并且在考试前运行过此题目的程序。题目是:求函数F=1+1/2+1/3+……+1/n的递归出口和递归体。
在这里先提一下递归模型:
递归模型:
由递归体与递归出口组成
{
if(递归出口)
(简单操作);
else
(递归体);
}根据题目写的c程序如下:
/*****************************************
求函数F=1+1/2+1/3+……+1/n
运行环境:Turbo 2.0&&Turbo C for Windows
Firedy
2007-1-8
******************************************/float fun(int n) /*递归函数*/
{
/*float k=1.0/n;*/
if(n==1) /*递归出口*/
return 1;
else
return fun(n-1)+1.0/n;/*k+=fun(n-1);*/ /*递归体*/
}main()
{
int n;
float F;
printf("F=1+1/2+1/3+...+1/n=?/n");
printf("/ninput n(n!=0):");
scanf("%d",&n);
F=fun(n);
printf("/nF=%.3f",F);
}运行结果:
从中可以看出递归的优点,接着说下教材里(我使用的c数据结构教材是西电科大出版的耿国华等编著的《数据结构--C语言描述》)提到的递归算法到递归算法的转换:
递归算法有两个特性:(1)递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法的分析方法是有效的。 (2)递归算法的时间效率底。(计算机编程很讲究算法的效率问题,也许所以就有了需要消除递归的原因,对这方面的理解,我没有怎么去思考,毕竟目前我们为了完成题目,首先是找思维直观,容易想到的方法,而对于效率的或效益的问题,更多的是企业或更进一步的研究学习是应该很重视的一个问题,可能这也可以说是我们学校的教育与社会之间的差距吧。)
其实,一个问题的思考,可以延伸到很多领域,研究研究是永无止境的
-
python递归函数的使用方法及实例_Python 递归函数详解及实例
2021-01-30 05:00:49Python 递归函数如果一个函数体直接或者间接调用自己,那么这个函数就称为递归函数.也就是说,递归函数体的执行过程中可能会返回去再次调用该函数.在python里,递归函数不需要任何特殊的语法,但是它需要...Python 递归函数
如果一个函数体直接或者间接调用自己,那么这个函数就称为递归函数.也就是说,递归函数体的执行过程中可能会返回去再次调用该函数.在python里,递归函数不需要任何特殊的语法,但是它需要付出一定的努力去理解和创建.
我们会以一个简单的例子开始:写一个函数求一个自然数中所有数字的和.在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法.在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分.
18117的数字和为:1+8+1+1+7=18.这样我们就可以分割这个数.把这个数分割成最低位7和不包含最低位数字的和1+8+1+1=11.这种分割方法给我们提供了一个算法:通过最低位n%10与n//10的数字之和相加来计算数n的数字之和.这种方法存在特殊情况:如果一个数只有一位,那么它的数字之和就是它本身.这个算法可以用递归函数实现.
def sum_digit(n):
"""return the sum of the digit of positive integer n."""
if n < 10:
return n
else:
last = n % 10
all_but_last = n // 10
return sum_digit(all_but_last) + last
函数sum_digit的定义是完整和正确的,即使sum_digit函数在自身的函数体里被调用.
这样求一个数的数字之和的问题就被分解成了两部分:求除去最低位部分数字之和,然后加上最低位.这两个步骤全都比原问题要简单.这个函数是递归的,因为第一步的问题和原问题是相同类型的.也就是说,sum_digit的确实是我们需要去实现自然数数字求和的函数.
我们可以理解这个递归函数是怎样使用计算环境模型成功应用的.它 不需要任何新的规范.
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
您可能感兴趣的文章:浅谈Python中的可迭代对象、迭代器、For循环工作机制、生成器Python进阶之递归函数的用法及其示例Python递归函数定义与用法示例浅析python递归函数和河内塔问题讲解Python中的递归函数python实现斐波那契递归函数的方法提升Python效率之使用循环机制代替递归函数
-
递归函数(二):编写递归函数的思路和技巧
2017-03-27 19:02:09递归函数(一):开篇递归函数(二):编写递归函数的思路和技巧递归函数(三):归纳原理递归函数(四):全函数与计算的可终止性递归函数(五):递归集与递归可枚举集递归函数(六):最多有多少个程序递归函数...递归函数(一):开篇
递归函数(二):编写递归函数的思路和技巧
递归函数(三):归纳原理
递归函数(四):全函数与计算的可终止性
递归函数(五):递归集与递归可枚举集
递归函数(六):最多有多少个程序
递归函数(七):不动点算子
递归函数(八):偏序结构
递归函数(九):最小不动点定理- -
递归,是一个熟悉而陌生的概念,说它熟悉,是因为人们经常提起它,
而说它陌生,指的是人们在实际编程中几乎不会主动使用它。给定一个问题,如果本质上它能看做一个调用自身的规模较小的一个子问题来求解,
那么给出一个递归的算法解,就是很自然的。
然而,即使是这样,编制一个递归函数也是一件令人头疼的事情。本系列文章的目的,可能并不局限于指出如何编写一个递归函数,
而是期望想从递归函数开始,了解它相关的科学知识,以达到对不同领域触类旁通的效果。从一个简单的例子开始
首先,我们来重温一下递归的概念,
维基百科上是这样描述的,递归(recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
我们来看一个简单的例子吧。(Haskell代码
fact :: Int -> Int fact 1 = 1 fact n = n * fact (n-1)
在这个例子中,
第一行fact :: Int -> Int
表示了fact
函数的类型,
第二行和第三行定义了函数fact
,
我们看到第三行,在对fact
函数定义的时候,等式右边又出现了fact
,
这样定义的函数fact
是递归的。我们调用一下
fact
,来看看结果,fact 10 3628800
嗯嗯,
fact
就是阶乘函数。写递归函数的步骤
那么,给定一个问题,我们编写一个递归函数,要如何开始呢?
(1)递推式
首先,我们要找到“递推式”。
例如,在数学上阶乘的定义是,\(f(n)=n!\),这样的表述形式,不具有递推性。
我们先要想办法把\(f(n)\)用\(f(n-1)\)表示出来。经过思考之后,我们可以证明,\(f(n)=n*f(n-1)\),
于是,我们就走出了关键的第一步,得到了“递推式”。(2)找出终止条件
有了“递推式”还不行,我们还需要确定递推在什么时候终止。
我们知道\(f(1)=1\),\(f(2)=2f(1)\),\(f(3)=3f(2)\),等等,
因此,我们只需要指定\(f(1)=1\),那么递推就会在\(f(n)\),当\(n=1\)的时候终止了。终止,就是不再调用规模更小的问题了。
这时,终止条件是\(f(1)=1\)。(3)用数学归纳法证明解的正确性
这一步是很重要的,有很多人都缺少证明递推式正确性的环节,
但是,考虑到介绍数学归纳法及其扩展会占用不少篇幅,
这里先略去,下一篇我们再回来讨论它。这里,我们先假定,根据“递推式”和“终止条件”,使用数学归纳法,
我们已经证明了这样定义的\(f(n)\)就是\(n!\)。(4)根据递推式和终止条件,编写程序
有了“递推式”和“终止条件”,再编写程序就水到渠成了。
很多人一上来就开始编码,就会感觉毫无头绪。我们再来看下那段程序,
fact :: Int -> Int fact 1 = 1 fact n = n * fact (n-1)
这不就是“递推式”和“终止条件”的忠实表示吗?
我们用fact 1 = 1
表示了\(f(1)=1\),
用fact n = n * fact (n-1)
表示了\(f(n)=n*f(n-1)\)。小技巧
我们再看个复杂一点的例子。
在实际项目中,我们可能会遇到循环n次的场景,
在循环过程中,我们会根据索引进行运算,然后将某些符合条件的运算放到最终的结果中。例如,我们选择10以内的所有偶数,
[x|x <- [0..9], x `mod` 2 == 0] [0,2,4,6,8]
使用以上列表解析(list comprehension)的方法,我们可以快速得到结果。
但是这里,我们想要拿它来举例,介绍一个编写递归函数常用的小技巧。为了通用性,我们考虑循环
n
次,将索引传入函数fn
,根据fn
的返回值,将结果放入一个列表中。(1)困境
根据前文介绍的编写步骤,我们需要先找到“递推式”和“终止条件”。
“终止条件”怎么写呢?
假如我们定义的递归函数称为myLoop
,那么\(myLoop(0,fn)\)就是终止条件,它应该返回一个列表。
但是这个列表在参数中没有,它随着递归调用的过程“积累”得到的。好吧,那我们看“递推式”。
\(myLoop(n,fn)\)要用\(myLoop(n-1,fn)\)的结果计算出来,
我们需要先用索引调用fn
,然后再根据fn
的返回值,放入结果列表,再继续调用\(myLoop(n-1,fn)\)。
可是,索引从哪来呢?(n
不是索引,因为索引从0开始,而n是逐渐变小的。这是两个典型的困难,
其一,我们在递归的过程中“积累”了某些东西,
其二,我们需要传递和递归过程相关的“索引”。(2)解法
这时候,我们的小技巧就有用武之地了。
我们可以编写一个辅助的递归函数,通过增加参数的办法,提高灵活性。
例如,我们可以编写一个辅助函数
myLoop'
,然后用myLoop'
来实现myLoop
。myLoop :: Int -> (Int -> Maybe a) -> [a] myLoop n fn = myLoop' n 0 fn [] myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a] -> [a] myLoop' 0 i fn lst = lst myLoop' n i fn lst = case fn i of Just x -> myLoop' (n-1) (i+1) fn (lst++[x]) Nothing -> myLoop' (n-1) (i+1) fn lst
以上,我们为
myLoop'
增加了参数i
和lst
,分别表示“索引”和“积累”的列表。
然后,myLoop
就可以用myLoop'
来实现了。别忘了测试一下最终的结果,
myLoop 10 (\x -> if x `mod` 2 == 0 then Just x else Nothing) [0,2,4,6,8]
(3)其他考虑
合理的利用递归函数的返回值,会减少附加参数的数量,例如,
myLoop :: Int -> (Int -> Maybe a) -> [a] myLoop n fn = myLoop' n 0 fn myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a] myLoop' 0 i fn = [] myLoop' n i fn = case fn i of Just x -> x:(myLoop' (n-1) (i+1) fn) Nothing -> myLoop' (n-1) (i+1) fn
但最终得到的递归函数就不是尾递归了,
关于尾递归,我们将在后续文章中讨论它。参考
-
JS中递归函数 JS函数相关及递归函数的使用
2018-03-16 14:59:30JS中的递归函数详解: 举个例子,1+2+3+4+5=?,用递归函数来完成; function fn(n){ if(n){ return 1; }else{ return n+fn(n-1) } } console.log(fn(5)) 我们把fn(5)解剖开,得出,不满足n,所以执行的是 ... -
Python 递归函数
2018-09-12 11:41:25递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 递归函数特性: 必须有一个明确的结束条件; 每次进入更深一层递归时,问题规模相比上次递归都应有所减少 ... -
关于递归函数转换为非递归函数的一些方式
2020-01-01 14:39:04关于递归函数转换非递归函数的一些方式前言目的可行性转换的几种途径 前言 最近在重拾算法和数据结构的一些知识,打算从基本的树的遍历算法入手。网上翻看了很多的二叉树的遍历算法相关文章,二叉树的遍历有前、中、... -
Python 实现递归函数求解分段函数表达式;并解释递归函数其原理
2019-03-31 13:46:03分段函数的题目是: 现在用代码将它表现出来: ''' 时间:2019/3/31 P(n)={1 ,n=1 ...要求:算法中不能出现'+','*','/'符号,并且用递归的思路作答, 写出两种实现方法:递归函数 和 非递归函数... -
MATLAB递归函数
2019-04-05 12:17:38MATLAB递归函数 递归函数就是函数调用自己本身,具体来说就是在一个函数模块里(设函数模块为factor.m,),存在函数(factor),这个函数(factor)用来调用函数模块(factor.m)。看下面的例子: 递归函数求n的... -
递归函数计算
2020-03-10 22:24:28递归的另一个优点是,递归函数不会受到怀疑,较非递归函数而言,某些人更相信递归函数。 递归函数必须定义一个终止条件;否则,函数就会“永远”递归下去,这意味着函数会一直调用自身直到程序栈耗尽,这种“永... -
C语言递归函数
2018-09-03 14:14:21递归函数是C语言的一大特点,也是C语言的一个重要知识点; 递归函数往往遵循着公式(例如等比数列,等差数列等); 最重要了解递归的这么一个思想; 什么是递归函数 从功能上来看:递归函数是一个函数,C语言中... -
什么是递归函数?
2018-02-21 09:42:10递归函数 递归 例题 特点 效率 优点 递归函数 递归 递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。递归函数必须有结束条件。 当函数在一直... -
递归函数、嵌套函数
2019-03-09 20:28:52递归函数 递归函数指的是:自己调用自己的函数,在函数体内部直接或间接的自己调用自己。递归类 似于数学的“数学归纳法”。 每个递归函数必须包含两个部分: 1. 终止条件 表示递归什么时候结束。一般用于返回值,... -
递归函数里面又有2个调用自身的递归函数里面参数变化总结
2016-08-12 23:52:48递归函数里面又有2个调用自身的递归函数里面参数变化总结 我们经常看见 public void f(int i){ //逻辑代码 f(i+1) f(i+1); } public void f(Queue queue){ //逻辑代码 f(queue); f(queue); } -
python递归函数
2019-06-27 00:17:05python 递归函数 一、何为递归函数 简单说就是:“函数自己调用自己”。 1 递归函数流程图 2 递归函数实例 # 例如 # 先定义一个函数 def f1(n): """ 用来计算某个数的阶乘 :param n: a class "int" ...