Meeting 05 - Recursion

Bor-Yuh Evan Chang

Tuesday, September 10, 2024

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

Meeting 05 - Recursion

In-Class Slides
In-Class Jupyter
Book Chapter

Announcements

• HW 1 + Quiz 1 was due Friday 9/6 Monday 9/9 6pm
  • How was it? Do you want to go over parts of it?
• Lab 1 due this Friday 9/13 6pm
  • Use GitHub and VS Code: Submit Lab1.scala. Just read Jupyter notebook or use it for scratch work.

Announcements

• A proposal: Lawrence (CM) will come to the classroom (ECCR 265) 1:45-2 and 3:15-3:30 for his “administrative office hours” so that you can more easily get your administrative issues resolved.
• A proposal: Would you go to evening review sessions run by your CAs? Think: an extra, optional recitation to review a planned topic (e.g., go over solutions to a past assignment, do extra practice on a difficult topic)

Announcements

• Bug in assertion for eval on 0 / 0 test in Lab1Spec.scala.
  • If you accepted the assignment to create your homework repo after 1:30am this morning, you have the updated version.
  • If you have the old version, the easiest way to update is to download the new version from https://github.com/csci3155-f24/pppl-lab1/blob/main/src/test/scala/jsy/lab1/Lab1Spec.scala.

Today

• Triage Your Questions
  • HW1?
• Preview Lab 1 (using coding.csel.io)
• Questions on Binding and Scope: A Scala crash course.
• Parts of Data Types: A Scala crash course.
• Recursion: A Scala crash course.

Your Questions?

• Review:
  • How do environments (type or value) relate to scope?
  • What is Nil, ::, and foreach?

Your Questions?

Factorial

defined function factorial
res1_1: Int = 6

Factorial: Some Evaluation Steps

factorial(3) \(\longrightarrow^\ast\) if (3 == 0) 1 else 3 * factorial(3 - 1)

\(\longrightarrow^\ast\) 3 * factorial(2)

\(\longrightarrow^\ast\) 3 * 2 * factorial(1)

\(\longrightarrow^\ast\) 3 * 2 * 1 * factorial(0)

\(\longrightarrow^\ast\) 3 * 2 * 1 * 0

\(\longrightarrow^\ast\) 6

Factorial: Pattern Matching

defined function factorial
res3_1: Int = 6

Factorial: Preconditions

java.lang.IllegalArgumentException: requirement failed
  scala.Predef$.require(Predef.scala:325)
  ammonite.$sess.cmd5$Helper.factorial(cmd5.sc:2)
  ammonite.$sess.cmd5$Helper.<init>(cmd5.sc:8)
  ammonite.$sess.cmd5$.<clinit>(cmd5.sc:7)

defined function factorial
res6_1: Int = 6

Factorial: Tail Recursive

defined function factorial
res8_1: Int = 6

Tail-Recursive Factorial: Some Evaluation Steps

factorial(3) \(\longrightarrow^\ast\) loop(1, 3)

\(\longrightarrow^\ast\) loop(1 * 3, 2)

\(\longrightarrow^\ast\) loop(3 * 2, 1)

\(\longrightarrow^\ast\) loop(6 * 1, 0)

\(\longrightarrow^\ast\) 6

Tail-Recursive Factorial

factorial(n = 3)
-->* loop(acc = 1, n = 3)
-->* loop(acc = 3, n = 2)
-->* loop(acc = 6, n = 1)
-->* loop(acc = 6, n = 0)
-->* 6

defined function factorial
res9_1: Int = 6

Exercise: Exponentiation

defined function exp
res11_1: Int = 16

defined function exp
res12_1: Int = 16

Exercise: Tail-Recursive Fibonacci

defined function fibonacci
res13_1: Long = 13L

defined function fib
res15_1: Long = 13L
res15_2: Long = 1298777728820984005L