Fonctions récursives (avec R)

Les fonctions récursives sont des fonctions qui s’appellent elle mêmes lors de leurs exécution voir: https://fr.wikipedia.org/wiki/Fonction_r%C3%A9cursive.

Un des challenges posé par Cédric sur son site: http://cedric-pupka.com/?p=117 , nous mets au défi de crée une fonction factorielle qui est récursive.

Voici une solution en R:

#factoriel récursive
f<-function(x){
  tmp<-1
  if(x>0){
    tmp<-f(x-1)*x
  }
  return(tmp)
}
#example
f(5)
#test
factorial(5)  

Comprendre le comment du pourquoi que sa marche est plutôt compliqué et brûle les neurones, j’imagine sa comme des poupées russe, lorsqu’on appelle f(3), la fonction
va appelée f(2) qui elle même appelle f(1).

Merci pour le challenge Cédric.

Advertisements

2 thoughts on “Fonctions récursives (avec R)

  1. Ta fonction semble coincider avec prod(1:n), mais diverge vite de factorial(n) – qui marche mal, en fait,

    > f(50)==prod(1:50)
    [1] TRUE
    > f(50)==factorial(50)
    [1] FALSE
    > f(50)==gamma(51)
    [1] FALSE

    il faudrait peut être aussi comparer avec ­factorialZ(n) ou prod(as.bigz(1:n)) de library(gmp) pour des valeurs de n encore plus grande…

    1. Merci Arthur pour votre commentaire stimulant voici le résultat de comparaison entre les quatres fonctions que vous proposez:

      f<-function(x){
      tmp0){
      tmp<-f(x-1)*x
      }
      return(tmp)
      }

      par(mfrow=c(2,2))
      #divergence from prod
      out_prod<-NULL
      for(i in seq(10,170,10)){
      out_prod<-c(out_prod,(f(i)-prod(1:i))/f(i))
      }
      plot(seq(10,170,10),out_prod)
      abline(h=0,lty=2,col="red")

      #divergence from factorial
      out_fact<-NULL
      for(i in seq(10,170,10)){
      out_fact<-c(out_fact,(f(i)-factorial(i))/f(i))
      }
      plot(seq(10,170,10),out_fact)
      abline(h=0,lty=2,col="red")

      #divergence from factorialZ
      library(gmp)
      out_factZ<-NULL
      for(i in seq(10,170,10)){
      out_factZ<-c(out_factZ,(f(i)-as.numeric(factorialZ(i)))/f(i))
      }
      plot(seq(10,170,10),out_factZ)
      abline(h=0,lty=2,col="red")

      #divergence from prod as.bigz
      out_bigZ<-NULL
      for(i in seq(10,170,10)){
      out_bigZ<-c(out_bigZ,(f(i)-as.numeric(prod(as.bigz(1:i))))/f(i))
      }
      plot(seq(10,170,10),out_bigZ)
      abline(h=0,lty=2,col="red")

      #all in one plot
      data<-as.data.frame(rbind(cbind(seq(10,170,10),out_prod,rep("prod",17)),cbind(seq(10,170,10),out_fact,rep("fact",17)),cbind(seq(10,170,10),out_factZ,rep("factZ",17)),cbind(seq(10,170,10),out_bigZ,rep("bigZ",17))))
      names(data)<-c("x","factorial_x","method")
      data[,1]<-as.numeric(levels(data[,1]))[data[,1]]
      data[,2]<-as.numeric(levels(data[,2]))[data[,2]]
      library(ggplot2)
      ggplot(data,aes(x=x,y=factorial_x,color=method))+geom_point()+geom_hline(xintercept=0,color="red",linetype="dashed")
      ggplot(subset(data,method!="fact"),aes(x=x,y=factorial_x,color=method))+geom_point()+geom_hline(xintercept=0,color="red",linetype="dashed")

      On voit bien que l'écart proportionnel entre la fonction récursive et factorial est le plus grand. Les trois autres méthodes donnent des patterns d'écart similaires avec un bias de plus en plus négatif lorsque l'on atteint les limites (au dela de f(170) R retourne Inf).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s