Geek Answers Handbook

Is the next function tail recursive?

I have a function in which the marked line is a conjunction involving a recursive call. Since the conjunctions work, if h1 <> h2 , then the recursive call will not be made. But if the call is completed, then the compiler will still refuse and execute a whole bunch of unions over the true values? Or will he overcome this unnecessary step?

In other words, is a recursive function efficient?

 let isExtensionOf<'A when 'A : equality> (lst1 : list<'A>) (lst2 : list<'A>) : bool = let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool = match currLst1, currLst2 with | h1 :: _, [] -> false | [], _ -> true | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2) // * helper lst1 lst2

Yes, I know that the highlighted line should be written if h1 = h2 then helper t1 t2 else false . But I'm just curious.

Thanks in advance.

+7
recursion tail-recursion f #
source share
2 answers

Another simple trick to figure out if a function is tail recursion is to throw an exception and look at the stack trace. For example, you can change helper as follows:

 let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool = match currLst1, currLst2 with | h1 :: _, [] -> failwith "!" | [], _ -> failwith "!" | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2)

If you now call helper [1..10] [1..10] , you get a stack trace that looks like this:

System.Exception :!
in FSI_0002.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
$ FSI_0003.main @ () Stopped due to an error

But if you change the code to non-tail-recursive - for example, by changing the last line to make the recursive call first (helper t1 t2) && (h1 = h2) , then the stack trace displays all the recursive calls:

System.Exception Error :! in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
in FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: line 4
. $ FSI_0005.main @ ()

+7
source share

From ILSpy, it looks like this:

  IL_0000: nop IL_0001: newobj instance void class '<StartupCode$ConsoleApplication3>.$Program'/ helper@10 <!!A>::.ctor() IL_0006: stloc.0 IL_0007: ldloc.0 IL_0008: ldarg.1 IL_0009: ldarg.2 IL_000a: tail. IL_000c: call !!0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>>::InvokeFast<bool>(class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!1, !!0>>, !0, !1) IL_0011: ret
+6
source share

More articles:


All Articles