#set document(title: "12.2 Simple math recursion", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 12.2#h(0.6em)Simple math recursion === Learning objectives By the end of this section you should be able to - Identify a recursive case and a base case in a recursive algorithm. - Demonstrate how to compute a recursive solution for the factorial function. === Calculating a factorial The factorial of a positive integer is defined as the product of the integer and the positive integers less than the integer. Ex: 5! = 5 \* 4 \* 3 \* 2 \* 1 Written as a general equation for a positive integer n: n! = n \* (n - 1) \* (n - 2) \* . . . \* 1 The above formula for the factorial of n results in a recursive formula: n! = n \* (n - 1)! Thus, the factorial of n depends upon the value of the factorial at n - 1. The factorial of n can be found by repeating the factorial of n - 1 until (n - 1)! = 1! (we know that 1! = 1). This result can be used to build the overall solution as seen in the animation below. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Finding the factorial of 5] #link("https://www.openstax.org/r/finding-factorial")[Finding the factorial of 12.3.1; ch 12, video 3] ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Recognizing recursion] Can the following algorithms be written recursively? ] === Defining a recursive function Recursive algorithms are written in Python as functions. In a recursive function different actions are performed according to the input parameter value. A critical part of a recursive function is that the function must call itself. A value for which the recursion applies is called the #strong[recursive case]. In the recursive case, the function calls itself with a smaller portion of the input parameter. Ex: In the recursive function factorial(), the initial parameter is an integer n. In the function's recursive case, the argument passed to factorial() is n - 1, which is smaller than n. A value of n for which the solution is known is called the #strong[base case]. The base case stops the recursion. A recursive algorithm must include a base case; otherwise, the algorithm may result in an infinite computation. To calculate a factorial, a recursive function, factorial() is defined with an integer input parameter, n. When n \> 1, the recursive case applies. The factorial() calls itself with a smaller argument, n - 1. When n == 1, the solution is known because 1! is 1; therefore, n == 1 is a base case. Note: 0! is defined to be 1; therefore, n == 0 is a second base case for factorial(). When n \< 1, an error is returned. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Factorial using recursion] #link("https://www.openstax.org/r/factorial-recursion")[Factorial using recursion; ch 12, video 4] ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Programming recursion] For the questions below, the function rec\_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec\_fact() if n = 17 is the initial input parameter? ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Recursive summation] Write a program that uses a recursive function to calculate the summation of numbers from 0 to a user specified positive integer n. ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Digits] Write a program that computes the sum of the digits of a positive integer using recursion. Ex: The sum of the digits of 6721 is 16. Hint: There are 10 base cases, which can be checked easily with the right condition. ]