## Types of Recursion

Kineese
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

### Types of Recursion

In the sample-exam of the lecture SS11 (find it here) on page 3 Ex. 3.1 there is a question about 4 different kinds of recursion-implementation.

Well at the moment I just figured out two types:
1. Usage the base languages recursion pattern --> Meta Interpreter
2. Usage of FixPoints
Heres the first type:

Code: Alles auswählen

 def interp(...) : ...{
...
case Rec(...) =>  interp(boundBody, cycBindAndInterp(boundId, namedExpr, env))
...
}
def cycBindAndInterp(...) = {
lazy val recEnv: Env = (id: Symbol) => {
if (id == boundId) interp(namedExpr, recEnv)
else env(id)
}
recEnv
}

The second type (fixpoint) is to difficult to write it down here

But what are the other two types of recursion?

Greets

K.

JanPM
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25

### Re: Types of Recursion

Hi, we asked the tutor today and agreed that the other two are:

-using state of the interpreted language (boxes)
-using state of the interpreting language (var)

Kineese
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

### Re: Types of Recursion

JanPM hat geschrieben:Hi, we asked the tutor today and agreed that the other two are:

-using state of the interpreted language (boxes)
-using state of the interpreting language (var)
Thanks for the response!
Is this mentioned somewhere in the slides or can you give a rough description how the recursion should looks like when using these styles?
I think that the usage of boxes is to store the variables for recursive calls, am I right?

JanPM
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25

### Re: Types of Recursion

Hi, there is an example in the GC_SRCFWAEInterp:

This is an example of using state of the INTERPRETED language. They first put a dummy value in the store. Then the namedExpr evaluates to a closure and the environment of that closure contains a pointer to the dummy. Afterwards the dummy gets replaced by the closure. So the env in the closure has a pointer to the closure itself.

Code: Alles auswählen

    /**
* In our stateful language, we do not require mutation from the
* host language to implement cyclic environments.
*/
case Rec(boundId, namedExpr, boundBody) => {
val (newLoc,s2) = store.malloc(stack, NumV(0))
val extStack = Map(boundId -> newLoc) :: stack
val (namedVal, bodyStore) = interp(namedExpr, extStack, store)
interp(boundBody, extStack, bodyStore.update(newLoc, namedVal))
}

Edit: I mean interpreted language

keksberg
Windoof-User
Beiträge: 30
Registriert: 4. Okt 2010 15:55

### Re: Types of Recursion

https://repository.st.informatik.tu-darmstadt.de/2012/copl/public/exam/check-list.pdf hat geschrieben:Explain the strategy of implementing recursion by means of [global function
declarations/lazy evaluation/immediate substitution/dynamic scoping/cyclic
environments/meta-interpretation]