Back to Questions
1.0k
views8
comments
Recursive function which is not recursive
f#compiler

One more question about my createWalker function. The compiler forces me to mark it as recursive, while in reality it is not recursive. As you can see in the function definition I posted below the function is passed to the repeater to be called later, but it is never called recursively directly or indirectly. I am curiuos why the compiler forces my hand here and what is the penalty for marking a function recursive when it is not

1
2
3
4
5
6

let rec createWalker (first:bool) (walker:Walker) (enumerator: obj seq) =
    {walker with 
        parent = Some walker; 
        nodes = bodyNodes @ [(Repeater(Seq.skip 1 enumerator, createWalker false) :> Django.Interfaces.Node)];
        context = enumerator |> Seq.hd |> createContext first walker
        }
.

Making a function recursive means that the identifier you are binding the function to will be valid as a binding for that function, in the definition of the function. It has nothing to do with if you actually "call" it. (Not to mention, you do actually call it: "createWalker false" applies with the first arg.)

Consider:

1
2
3
4
5
6
7
8
9
10

 

 let test() =
   let foo n = n + 1
   let foo n = foo n - 1
   printfn "%A" <| foo 1
   let rec foo n = foo n - 1
   printfn "won't happen %A " <| foo 1
   ()

The first two definitions work fine -- there's no recursion, so the second foo will call the original foo, then decrement (net zero). The last one, however, will recurse on itself forever.

By on 4/3/2009 2:20 PM ()

...

(Not to mention, you do actually call it: "createWalker false" applies with the first arg.)

...

Now I am thoroughly confused. What do you mean I call it?... Let me rephrase it - is there any expression defined in the body of the createWalker function which is executed at the time I pass it to the Repeater object?

By on 4/3/2009 3:12 PM ()

...

(Not to mention, you do actually call it: "createWalker false" applies with the first arg.)

...

Now I am thoroughly confused. What do you mean I call it?... Let me rephrase it - is there any expression defined in the body of the createWalker function which is executed at the time I pass it to the Repeater object?

Brian explained it well. I was referring to that, yes, you're still using it. Sorry for the confusion!

By on 4/3/2009 3:35 PM ()

Now I am thoroughly confused. What do you mean I call it?... Let me rephrase it - is there any expression defined in the body of the createWalker function which is executed at the time I pass it to the Repeater object?

In a sense,

let f x y = ...

means

let f = (fun x -> (fun y -> ...))

and so in this sense 'calling'

f 3

'evaluates' in that in 'computes' the resulting lambda that is the partial application of the function.

But in the sense you're asking, no, nothing gets 'called' before the 'final' argument gets passed.

By on 4/3/2009 3:16 PM ()

In a sense, 'evaluates' in that in 'computes' the resulting lambda that is the partial application of the function.

But in the sense you're asking, no, nothing gets 'called' before the 'final' argument gets passed.

That was how I understood it, thank you. It is good to know that I am not completely insane :)

By on 4/3/2009 3:37 PM ()

Basically 'let rec' says 'the following name is in scope immediately', whereas 'let' says that 'the following name is in scope after this binding'. Put another way, 'rec' means 'I can use the name on the left-hand-side inside the expression on the right-hand-side'.

Make sense?

By on 4/3/2009 2:17 PM ()

Basically 'let rec' says 'the following name is in scope immediately', whereas 'let' says that 'the following name is in scope after this binding'. Put another way, 'rec' means 'I can use the name on the left-hand-side inside the expression on the right-hand-side'.

Make sense?

You are saying the let rec is about the name visibility at compile time rather than runtime limitations. It probably means that there is no runtime penalty for this - right?

By on 4/3/2009 3:00 PM ()

You are saying the let rec is about the name visibility at compile time rather than runtime limitations. It probably means that there is no runtime penalty for this - right?

Right.

By on 4/3/2009 3:06 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper