微信号:gh_61e2455df34c

介绍:介绍R语言的学习和使用,关注数据挖掘算法,利用R语言实现常见的数据挖掘算法,并配以有趣的NBA数据分析案例.不管您是初学还是精通R语言,本平台都致力于让您能从中获益.

递归函数浅析

2016-06-29 18:12 飞刀

递归定义

递归就是在函数运行的过程中直接或者间接调用自己的一种编程技巧。

它通常是把一个复杂的问题通过抽象层层转化为一个与原问题相似的规模较小的问题来求解(类似于数学中所说的通项)。

递归的好处是仅需少量的程序代码便可描述出复杂问题所需要的多次重复计算,使程序看上去更简洁。

编写递归函数

一般来说,递归主要包括边界条件、递归前进段和递归返回段。递归调用时,若边界条件不满足,递归前进;若边界条件满足时,则递归返回。

我这么说你可能还不太明白,我举个栗子,比如1,2,3,...,n的自然数求和问题。我以f(n)来表示前n项的和,容易知道f(n)=n+f(n-1),f(n-1)=n-1+f(n-2),...,f(3)=3+f(2),f(2)=2+f(1),f(1)=1。

于是我们可以定义如下递归函数:

mysum <- function(x){

  if(x==1){

    res = 1  #设置边界条件

  } else {

    res <- x + myfun(x-1)  # 递归

  }

  return(res)  # 返回

}

还有另外一种实现,采用R自带的Reduce函数,它有三个主要的参数,f表示递归函数,init设置初始值,x一般为数值型向量。上述求和可用如下代码简化:

mysum <- function(n) Reduce(f = sum,init = 0,x = 1:n)

在R console上运行mysum(100)你就会得到5050。

递归案例

另下面有三个经典的递归案例,斐波那契数列、汉诺塔、杨辉三角,你也可以尝试地实现,代码附上。

斐波那契数列

myfun <- function(n){

  if(n==0){

    return(0)

  } else if(n==1){

    return(1)

  } else {

    return(myfun(n-1)+myfun(n-2))

  }

}

汉诺塔

hanoi <- function(n,x,y,z){

  if(n==1){

    print(paste(x,'-->',z,sep=" "))

  } else {

    hanoi(n-1,x,z,y) #将前n-1个盘子从x移动到y上 

    hanoi(1,x,y,z) #将最底下的最后一个盘子从x移动到z上 

    hanoi(n-1,y,x,z) #将y上的n-1个盘子移动到z上 

  }

}

杨辉三角

triangles <- function(n){

    if(n == 1){

      print(1)

    } else {

      t <- triangles(n-1)

      t1 <- c(0,t)

      t2 <- c(t,0)

      print(t1+t2)

    }

}



 本文来自飞刀的微信公共帐号“数据挖掘与R语言”,用微信添加数据挖掘与R语言公众号,即可订阅。转载必须保留作者、公共帐号信息。 

长按识别图中二维码



 
数据挖掘与R语言 更多文章 线性回归与R语言 数据类型与数据结构 编写属于你自己的R函数 数据处理之——plyr xgboost:速度快效果好的Boosting模型
猜您喜欢 我们在默默地为你改变 喜大普奔,PHP7正式发布! greenplum导入数据的几种方法 作为高级Java,你应该了解的Linux知识 书接上文:薛定谔的猫是如何诞生的?