lab
EECS 280 Lab 09: Recursion
Lab Due Sunday, November 15, 2020, 8:00 pm
Direct autograder link
In this lab, we will practice recursion by implementing functions using iteration (loops) and recursion. You will also write tail recursive functions to understand their relationship to iterative solutions. Finally, we’ve prepared an Exam Prep that reviews similar topics.
You may work alone or with a partner. Please see the syllabus for partnership rules.
Submit the code files below on the autograder. We encourage you to complete the lab Exam Prep, but it is not turned in for credit.
Files to submit
lab09.cpp
Completion Criteria/Checklist:
To pass this lab, you must finish tasks 1 and 2.

(Task 1) Implement
hailstone
andhailstone_iter
. 
(Task 2) Implement
count_digits
,count_digits_iter
, andcount_digits_tail
.
Lab Exercises
The Files
We have provided starter files for this lab. Use the following commands in a terminal at your working directory to download the files.
$ wget eecs280staff.github.io/lab/lab09/starterfiles.tar.gz
$ tar xvzf starterfiles.tar.gz
Here’s a summary of this lab’s files. You will turn in the bolded ones.
File  Description 

lab09.h 
Contains the hailstone and count_digit function declarations. 
lab09.cpp 
Contains the hailstone and count_digit function definitions. 
main.cpp 
Contains the main function that runs testing code. 
Testing Code
The main
function in main.cpp
contains some testing code we’ve written for you, which will print the results produced by your code.
The starter code should compile successfully without any modifications, so make sure you are able to compile and run it with the following commands. The code may be missing some pieces, contain some bugs, or crash when you run it, but you’ll fix each throughout the course of the lab.
$ g++ Wall Werror g pedantic std=c++11 lab09.cpp main.cpp o lab09.exe
$ ./lab09.exe
Introduction
Task 1  Hailstone Sequence
Pick any positive integer n
. If n
is even, compute n/2
. If n
is odd, compute 3n+1
. Take the result as the new n
and continue the process, but stop if you get to 1
. For example, if we start at n = 7
the sequence is:
7, 22, 11, 34 ,17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Such a sequence of numbers is called a hailstone sequence. (Any guesses why?)
In formal terms, the hailstone sequence starting at n is defined by the recurrence relation:
\[\begin{gather} a_i = \begin{cases} n~ &\textrm{for}~ i = 0\\ f(a_{i1})~ &\textrm{for}~ i > 0 \end{cases}\\ \textrm{where}\\ f(n) = \begin{cases} n/2~ &\textrm{if}~ n \equiv 0 \pmod{2}\\ 3n+1~ &\textrm{if}~ n \equiv 1 \pmod{2} \end{cases} \end{gather}\]The Collatz conjecture states that every hailstone sequence eventually ends in 1. The conjecture remains unproven to this day, but most mathematicians believe it to be true.
Your task is to write functions that print the hailstone sequence for a given value of n
by filling in the function stubs provided in lab09.cpp
. Your functions should print the whole sequence on a single line, with a space after each element (including the last one). Notice that hailstone
must be recursive while hailstone_iter
must use iteration.
Hint: Use the recurrence relation given above as a model for your recursive function.
Task 2  Digit Counting
Next you’ll write a function that counts the number of times a digit appears in a number. For example, the digit 2
appears in the number 20120130
two times. You must write three variations of this function, once using “regular” recursion (count_digits
), once using iteration (count_digits_iter
) and once using a tail recursive helper function (count_digits_tail
). Again, just fill in the function stubs in lab09.cpp
with your code.
Hint: n % 10
gives you n
’s last digit (134 % 10 = 4
), while n / 10
removes n
’s last digit (134 / 10 = 13
).
Submit
Submit the required files to the autograder.