#set document(title: "12.4 More 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.4#h(0.6em)More math recursion


  
    
=== Learning objectives


    By the end of this section you should be able to


    - Define a recursive function to generate Fibonacci numbers.


  
  
    
=== Fibonacci sequence using recursion


    The Fibonacci sequence is a sequence in which each number in the sequence is the sum of the previous two numbers in the sequence. The first two numbers are 0 and 1. Thus, starting from 0 and 1, the third number is 0 + 1 = 1, and the next number is 1 + 1 = 2. The sequence of numbers is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .


    Recursion can be used to calculate the nth Fibonacci number. The base cases are 0 and 1. Thereafter, the nth number is given by adding the (n - 1)th and (n - 2)th number. Thus, fib(n) = fib(n - 1) + fib(n - 2), which is a recursive definition ending with base cases f(0) = 0, and f(1) = 1.


    For a recursion that calls multiple functions in the recursive case, tracing how the recursion proceeds is useful. A structure used to trace the calls made by a recursive function is called a #strong[recursion tree]. The animation below traces the recursion tree for a call to a recursive function to calculate the Fibonacci number for n = 5.


    #examplebox("Example 1")[Finding the nth Fibonacci number][
The Fibonacci function recursion is more complex with the value at n depending on two function calls with smaller values.


      
    """ Recursive Fibonacci function """

    def fib(n):
      \# Base case
      if n == 0 or n == 1:
        return n
      \# Recursive case
      elif n \> 1:
        return fib(n - 1) + fib(n - 2)
      \# Error case
      else:
        print("Fibonacci numbers begin at 0.")
        return

    \# Test code
    print(fib(7))
      The above code's output is:


      
    13
]


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Recursive Fibonacci function]


      #link("https://www.openstax.org/r/recursive-Fibonacci-function")[Recursive Fibonacci function; ch 12, video 7]
]


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Fibonacci numbers]
]


  
  
    
=== Greatest common divisor (GCD)


    The greatest common divisor (GCD) of two positive integers is an integer that is a divisor for both integers. Ex: The GCD of 6 and 9 is 3 because 3 x 2 = 6, and 3 x 3 = 9.


    The GCD is found easily using Euclid's method. Euclid's method recursively subtracts the smaller integer from the larger integer until a base case with equal integers is reached. The greatest common divisor is the integer value when the base case is reached.


    #examplebox("Example 2")[Finding the GCD][
""" Find GCD using recursive implementation of Euclid's method """

    def gcd(a, b):
      if a == b: \# Base case
        return a
      elif a \< b: \# Recursive case
        return gcd(a, b - a)
      else:
        return gcd(a - b, a)

    \# Test code
    print(gcd(24, 30))
      The above code's output is:


      
    6
]


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[GCD]
]


  
  #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Recursive power]


    Write a recursive power() function, such that given an integer x and a positive integer y, power(x, y) returns x raised to y.


    Ex: power(3, 4) returns 81.


    x = int(input())
y = int(input())

\# TODO: power() function definition

print(power(x, y))
]


  #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Recursive power (with any integer power)]


    Write a recursive rec\_pow() function such that given two integers, x and y, it returns x raised to y.


    (Note: this is an extension of the above problem but now works for any integer value of y, positive or negative. How should the recursive function change to deal with a negative value of y?)


    Ex: rec\_pow(2, -4) returns 0.0625.


    x = int(input())
y = int(input())

\# TODO: rec\_pow() function definition

print(rec\_pow(x, y))
]