How to effectively render a recursive function?

Question

I am currently participating in recursion training in a programming class. I noticed how difficult it is for my students to understand the concept of recursion. Is there a good way to visualize what a function does for pedagogical purposes?

As an example, there is a function R to get the nth Fibonacci number:

fib_r <- function(n) { if(n <= 2) return(1) fib_r(n-1) + fib_r(n-2) } 

Thanks.

Answer 1

Here is how I would like to explain recursive functions in R :

First, I agree with @AEBilgrau that factorial is a good example of recursion. (Better than Fibonacci in my opionion.)

Then I would quickly go through the theoretical basis why a factorial can be defined as a recursive function, something simple, like

4! = 4 * 3 * 2 * 1 = 4 * 3!

Then you can present them with the corresponding recursive function R

 fact=function(x) if (x==0) return(1) else return(x*fact(x-1)) fact(3) #6 

, but also represent the following conclusion

 #|fact(3) called #|fact(3) is calculated via 3*fact(2) #|fact(2) is unknown yet. Therefore calling fact(2) now #|Waiting for result from fact(2) #| fact(2) called #| fact(2) is calculated via 2*fact(1) #| fact(1) is unknown yet. Therefore calling fact(1) now #| Waiting for result from fact(1) #| | fact(1) called #| | fact(1) is calculated via 1*fact(0) #| | fact(0) is unknown yet. Therefore calling fact(0) now #| | Waiting for result from fact(0) #| | | fact(0) called #| | | fact(0)=1 per definition. Nothing to calculate. #| | | fact(0) returning 1 to waiting fact(1) #| | fact(1) received 1 from fact(0) #| | fact(1) can now calculate 1*fact(0)=1*1=1 #| | fact(1) returning 1 to waiting fact(2) #| fact(2) received 1 from fact(1) #| fact(2) can now calculate 2*fact(1)=2*1=2 #|fact(3) received 2 from fact(2) #|fact(3) can now calculate 3*fact(2)=3*2=6 #[1] 6 

as obtained from

 #helper function for formatting tabs=function(n) paste0("|",rep("\t",n),collapse="") fact=function(x) { #determine length of call stack sfl=length(sys.frames())-1 #we need to define tmp and tmp1 here because they are used in on.exit tmp=NULL tmp1=NULL #on.exit will print the returned function value when we exit the function ... #... ie, when one function call is removed from the stack on.exit({ if (sfl>1) { cat(tabs(sfl),"fact(",x,") returning ", tmp," to waiting fact(",x+1,")\n",sep="") } }) cat(tabs(sfl),"fact(",x,") called\n",sep="") if (x==0) { cat(tabs(sfl),"fact(0)=1 per definition. Nothing to calculate.\n",sep="") #set tmp for printing in on.exit tmp=1 return(1) } else { #print some info for students cat(tabs(sfl),"fact(",x,") is calculated via ",x,"*fact(",x-1,")\n",sep="") cat(tabs(sfl),"fact(",x-1, ") is unknown yet. Therefore calling fact(",x-1,") now\n",sep="") cat(tabs(sfl),"Waiting for result from fact(",x-1,")\n",sep="") #call fact again tmp1=fact(x-1) #more info for students cat(tabs(sfl),"fact(",x,") received ",tmp1," from fact(",x-1,")\n",sep="") tmp=x*tmp1 cat(tabs(sfl),"fact(",x,") can now calculate ", x,"*fact(",x-1,")=",x,"*",tmp1,"=",tmp,"\n",sep="") return(tmp) } } fact(3) 

Answer 2

Here is my example, possibly used in several tutorials:

 recursive_sum <- function(n){ if(n == 1) {print("Remember 1, add everything together"); return(n)} print(paste0("Remember ", n, ", pass ", n-1, " to recursive function")) n + recursive_sum(n-1) } 

Output:

 > recursive_sum(4) [1] "Remember 4, pass 3 to recursive function" [1] "Remember 3, pass 2 to recursive function" [1] "Remember 2, pass 1 to recursive function" [1] "Remember 1, add everything together" [1] 10 

Answer 3

I think factorial function is a good example of recursion. Combining this with a printout (as others show) seems like a good way to describe what happens:

 factorial <- function(n) { cat("factorial(", n, ") was called.\n", sep = "") if (n == 0) { return(1) } else { return(n * factorial(n - 1)) } } factorial(4) #factorial(4) was called. #factorial(3) was called. #factorial(2) was called. #factorial(1) was called. #factorial(0) was called. #[1] 24 

Then you can also implement a non-recursive factorial function and compare computational efficiency. Or maybe ask them what is problematic with the above implementation (for example, what happens with factorial(-4) ).

As for more correct visualization (and not just simple examples), there are websites that illustrate the recursion tree.

Edit: Googling recursion is also a useful lesson.

Answer 4

Print the value of the variable n to fib_r

 print("iteraction at: ", n)