Week 4 - Recursive Algorithms.

YTI from last week

Last week I ended the week by asking you to, either on your own, or with a partner, attempt to use and modify my code to do a variety of different things. The material below is available if you want to check your work or see my answers.

• First, I asked you to compare how the sorts perform depending on how the original data is organized:
  • I walk through my code [video (15 minutes)]
  • https://replit.com/@CSED5320-F22/Week-3-Sample-Solution-Timer-Comparisons#main.py
• Then, I asked you to consider how you would modify the different sorts to behave differently.
  • Rather than create a video for this I am just going to show you my solutions.
  • Please reach out if you have questions.
  • https://replit.com/@CSED5320-F22/Week3-Sample-Solution-Modifications#main.py

Prep for Recursion

Reading Guide

Carefully and thoroughly read the material in sections 5.5-5.6 of your textbook (pp. 276-295).

Video Resources

• Hacker Rank : Algorithms:Recursion
• Discussion on Recursion
  • Reviewing Recursion (9 minutes)
  • Visualizing Recursion (7 minutes)
  • Writing/viewing a few recursive algorithms
    • isPalindrome (7 minutes)
      • Finished Code
    • Recursive BinarySearch (10 minutes)
      • Finished Code
    • Recursive Sudoku (11 minutes)
      • Finished Code

You Try It

In this activity I would like you and a partner to try to use what you just learned to create recursive algorithms in python for:

• Finbonacci (use the Hacker Rank video as a guide)
  • Fib(n) = Fib(n-1) + Fib(n-2) when n ≥ 2
  • Fib(1)=1
  • Fib(0)=1

• Reverse a string
  •