CODEWITHSUNDEEP
rrecursioninterpreter
user969113
user969113

Reputation: 2429

How and where are the interim results in a recursion stored?

I am trying to understand how recursion works in terms of the interpreter. Therefore, I implemented a simple recursion function in R:

> fac <- function(x) {
+   print(x)
+   if(x==0) return(1)
+   else {x*fac(x-1)}
+ }
> 
> fac(4)
[1] 4
[1] 3
[1] 2
[1] 1
[1] 0
[1] 24
>

I understand recursion itself but not how the interpreter stores the interim results. In this example we start with fac(4) which basically returns 4*fac(3) then 3*fac(2) and so on. But where or how are such interim results stored? Once the function does its final call which is 1*fac(0) it still needs to sum up the results from the previous calls. But again, these must be stored or kept in memory beforehand. I hope it's understandable what I am trying to ask. Not sure how to explain that properly...

Upvotes: 2

Views: 42

Answers (1)

Sylwester
Sylwester

Reputation: 48765

The state of every call stays in the stack. All the generations have their own version of x and every except the base case does a multiplication after the lower recursions are finished. This is called a continuation making this recursive function not possible to tail call optimize. The multiplication happens on the unrolling side after the base case hit.

Strange language if you have return in your base case but not return x*fac(x-1). Seems inconsistent.

Upvotes: 1

Related Questions