CS173: Intro to Computer Science - Recursion

Activity Goals

The goals of this activity are:
  1. To identify a recursive base case
  2. To implement recursive algorithms

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity


Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity on the Class Activity Questions discussion board. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Recursive Algorithms

Diagram of Fibonacci Recursive Calls


  1. Notice that the algorithm "starts over" on a smaller part of the array after each guess. This is a hallmark of a "recursive algorithm." They are like loops. Do you think this approach requires more or less code to write than a non-recursive version? Why or why not?
  2. How many times did this algorithm compute fib(2)?

Model 2: Base Cases and Recursive Steps


  1. Fill in the base case and recusive call for the factorial function, and try running it!

Embedded Code Environment

You can try out some code examples in this embedded development environment! To share this with someone else, first have one member of your group make a small change to the file, then click "Open in Repl.it". Log into your Repl.it account (or create one if needed), and click the "Share" button at the top right. Note that some embedded Repl.it projects have multiple source files; you can see those by clicking the file icon on the left navigation bar of the embedded code frame. Share the link that opens up with your group members. Remember only to do this for partner/group activities!

Reflective Journal Prompt

  1. How might you improve upon (reduce) the number of calls to fib(2) in the Fibonacci example?


Submit your answers to the questions using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.

For Additional Practice

Feel free to visit these resources for additional practice exercises.