编程辅导 Programs with "Repetition" in © 2018 by . All Rights Reserved.

Learning Outcomes
by the End of the Lecture, Students that Complete

the Recommended Exercises should be Able to:
Explain the Problem with Looping Control Structures Implement Looping Algorithms with Recursion Describe the Different Types of Recursion Practice Creating Looping Programs
Copyright © 2018 by . All Rights Reserved.

Reading and Suggested Exercises
Copyright © 2018 by . All Rights Reserved.
Read the following Chapter(s):
Chapter 5: “Hello recursion!” “Maximum awesome”

Control Structures
in many Procedural Languages, For (i.e., counter- controlled) and While (event-controlled) Loops are the Constructs by which Repetition is accomplished
with Referential Transparency, these Looping Control Structures are Not Possible
Copyright © 2018 by . All Rights Reserved.

at this point at this point
i has a value of 0 i has a value of 1
Control Structures
for i in range(2): print(i)
upon Execution, the Output would be:
Copyright © 2018 by . All Rights Reserved.

Control Structures
as a result of Referential Transparency, if i was Ever Equal to 0, then it Must Always Equal to 0
if i was Later considered Equal to 1, then by the Transitivity Property of Equality, 0 = 1 (which is obviously a contradiction)
(n.b., do not forget that there is no concept of “state” in functional programming)
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
Recursion is the Approach by which Repetition is accomplished in Functional Languages
Recursive Functions, by definition, are functions that Call Themselves, and (if properly designed) will Stop Recursing once a Base Case is reached
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
the Factorial of a Positive Integer is the Product of that Integer and All Lesser Positive Integers
the Factorial of Zero is Defined as One (because One is the Identity Element of Multiplication)
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
Iterative Definition
𝑛× 𝑛−1 × 𝑛−2 ×⋯×3×2×1
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
Iterative Definition
𝑛× 𝑛−1 × 𝑛−2 ×⋯×3×2×1
𝑛−1 × 𝑛−2 ×⋯×3×2×1
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
Iterative Definition
Recursive Definition
How Would this Function be Plotted (e.g., on a chart)?
𝑛× 𝑛−1 × 𝑛−2 ×⋯×3×2×1
𝑛−1 × 𝑛−2 ×⋯×3×2×1
(𝑛−1)× 𝑛−2 !
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
although the Factorial function is Discrete and Not Continuous (i.e., do not connect the points), it will help conceptually to Imagine Two Regions…
7 6 5 4 3 2 1 0
factorial 𝑥
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
𝐟𝐚𝐜𝐭:Z∗ →Z+
𝐟𝐚𝐜𝐭 𝒏 = ቊ 𝟏 𝐢𝐟 𝒏 = 𝟎 𝒏×𝒏−𝟏! 𝐢𝐟𝒏>𝟎
since the Definition for the Factorial Function uses Cases, How could it be Implemented in Haskell?
Copyright © 2018 by . All Rights Reserved.

Branching Control Structures first Create the Type Declaration:
then Create the Function Definition:
Copyright © 2018 by . All Rights Reserved.

Branching Control Structures first Create the Type Declaration:
fact :: Integer -> Integer
then Create the Function Definition:
| (n == 0) = 1
| (n > 0) = n * (fact (n-1))
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
a Problem with the Previous Definition is that Negative Integers are Within the Function Domain (as described in the Type Declaration) but
Fail to Pass Any of the Guards
this can be Addressed (albeit poorly) by Operationally Defining the Factorial of a Negative Integer as 0
Copyright © 2018 by . All Rights Reserved.

Recursive Functions first Create the Type Declaration:
fact :: Integer -> Integer
then Create the Function Definition:
| (n == 0) = 1
| (n > 0) = n * (fact (n-1)) | otherwise = 0
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
there is actually a very Elegant and Accurate way to Address this Problem (that we will Discuss Later)
How could we Implement the Same Function Without Guards?
Copyright © 2018 by . All Rights Reserved.

Recursive Functions first Create the Type Declaration:
fact :: Integer -> Integer
then Create the Function Definition:
if (n == 0) then 1
else if (n > 0)
then n * (fact (n-1)) else 0
Copyright © 2018 by . All Rights Reserved.

Recursive Functions
What would be the Evaluation Order for fact 4 (Assuming the Function Definition that used Guards)?
Copyright © 2018 by . All Rights Reserved.

| (n == 0) = 1
| (n > 0) = n * (fact (n-1))
~ 4 ~ 4 ~ 4 ~ 4 ~ 4 ~ 4 ~ 4 ~ 4 ~ 4 … ~ 24
Copyright © 2018 by . All Rights Reserved.
Recursive Functions
* fact (4 – 1)
* (3 * fact (3 – 1))
* (3 * fact 2)
* (3 * (2 * fact (2 – 1)))
* (3 * (2 * fact 1))
* (3 * (2 * (1 * fact (1 – 1)))) * (3 * (2 * (1 * fact 0)))
* (3 * (2 * (1 * 1)))

| (n == 0) = 1
| (n > 0) = n * (fact (n-1))
Copyright © 2018 by . All Rights Reserved.
Recursive Functions

Types of Recursion
Primitive Recursion is Defined only over Nonnegative Integers with a Base Case at 𝑛 = 0 and an Inductive Case at 𝑛 > 0 such that the Argument for Each Recursive Call is 𝑛 − 1
General Recursion does Not share these Constraints
• it may have More than one Base Case
• it may have More than one Recursive Call / Argument
• it may have Arguments that may Not be Strictly Smaller
Copyright © 2018 by . All Rights Reserved.

Types of Recursion
the Triangle of an Integer is Operationally Defined as the Sum of that Integer and All Lesser Positive Integers
How would you Implement this in Haskell… …using Guards?
…Without Guards?
Copyright © 2018 by . All Rights Reserved.

Types of Recursion first Create the Type Declaration:
triangle :: Integer -> Integer
then Create the Function Definition:
triangle n
| n > 0 = n + (triangle (n-1)) | otherwise = n
Copyright © 2018 by . All Rights Reserved.

Types of Recursion first Create the Type Declaration:
triangle :: Integer -> Integer
then Create the Function Definition:
triangle n =
if (n > 0)
then n + (triangle (n-1)) else n
Copyright © 2018 by . All Rights Reserved.

Types of Recursion
How would you Create a Recursive Implementation of Exponentiation in Haskell?
(n.b., you can use * for multiplication, but not the ^, ^^, or ** exponentiation operators)
Copyright © 2018 by . All Rights Reserved.

Types of Recursion Fibonacci Numbers represent the Growth of
a Population of Rabbits under Ideal Conditions
initially there is only One Pair of Immature Rabbits after the 1st Month there is One Pair of Mature Rabbits after the 2nd Month there are Two Pairs of Rabbits after the 3rd Month there are Three Pairs of Rabbits after the 4th Month there are Five Pairs of Rabbits
Copyright © 2018 by . All Rights Reserved.

Types of Recursion
the Definition for the nth Fibonacci Number would be Recursive, but would Not be an example of Primitive Recursion (i.e., it is General Recursion)
Why isn’t the nth Fibonacci Number function Primitive Recursion?
Copyright © 2018 by . All Rights Reserved.

Types of Recursion
the nth Fibonacci function has Two Base Cases
the 1st Fibonacci Number (i.e., n = 0) is 0 and the 2nd Fibonacci Number (i.e., n = 1) is 1
the nth Fibonacci function requires Two Recursive Calls when n > 2, the nth Fibonacci Number is the Sum of
the (n-1)th and the (n-2)th Fibonacci Numbers Copyright © 2018 by . All Rights Reserved.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts