Debian Codegraph @

tests/data/notebooks/outputs/ipynb_to_myst/tailrecursive-factorial.md

raw
1 ---
2 jupytext:
3 encoding: '// -*- coding: utf-8 -*-'
4 formats: ipynb,groovy:light
5 kernelspec:
6 display_name: Groovy
7 language: groovy
8 name: groovy
9 ---
10
11 # TailRecursive annotation
12
13 Let's check what is the effect of `@TailRecursive` annotation on the simple recursive definition of factorial function.
14
15 ```{code-cell}
16 import groovy.transform.CompileStatic
17 import groovy.transform.TailRecursive
18 import groovy.transform.TypeChecked
19
20 @CompileStatic
21 @TypeChecked
22 class X {
23 static final BigInteger factorial0(int n) {
24 (n <= 1) ? 1G : factorial0(n-1).multiply(BigInteger.valueOf(n))
25 }
26
27 static final BigInteger factorial1(int n, BigInteger acc = 1G) {
28 (n <= 1) ? acc : factorial1(n-1, acc.multiply(BigInteger.valueOf(n)))
29 }
30
31 @TailRecursive
32 static final BigInteger factorial2(int n, BigInteger acc = 1G) {
33 (n <= 1) ? acc : factorial2(n-1, acc.multiply(BigInteger.valueOf(n)))
34 }
35 }
36
37 x = new X()
38 ```
39
40 Although we can time the execution of the calls, it is not very accurate; such micro benchmarks should be performed in more controlled environment, such us under [JMH](https://openjdk.java.net/projects/code-tools/jmh/).
41
42 For example, see [blog posts of Szymon Stępniak](https://e.printstacktrace.blog/tail-recursive-methods-in-groovy/).
43
44 ```{code-cell}
45 %%timeit
46
47 x.factorial0(19_000).toString().length()
48 ```
49
50 ```{code-cell}
51 %%timeit
52
53 x.factorial1(19_000).toString().length()
54 ```
55
56 ```{code-cell}
57 %%timeit
58
59 x.factorial2(19_000).toString().length()
60 ```
61
62 The real difference is the use of stack. Non-tail recursive calls exhaust the stack space at some point, whereas tail recursive calls don't add frames to the stack.
63
64 ```{code-cell}
65 factSize = { n, cl ->
66 println "Factorial of ${n} has ${cl(n).toString().length()} digits"
67 }
68
69 factSize 2_000, x.&factorial0
70 factSize 2_000, x.&factorial1
71 factSize 2_000, x.&factorial2
72
73 factSize 100_000, x.&factorial2
74 ```
75
76 ```{code-cell}
77 try {
78 factSize 100_000, x.&factorial1
79 } catch (Throwable e) {
80 assert e instanceof StackOverflowError
81 println e
82 }
83 ```