EngGen 131 S2 2021
Lab 12 – 1 – Course Manual (C Programming)
ENGGEN 131 2021
Lab 12
Recursion
HAVE YOU COMPLETED THE PREPARATION EXERCISES?
Pages 173-176 of the coursebook contain the “Preparation Exercises” for this lab. You should
complete these exercises before you attempt the exercises in this lab. In particular, these preparation
exercises illustrate the basic concepts behind recursion.
GETTING STARTED
Download the .zip file called “Lab12Resources.zip” from Canvas. This file contains all of the
resources that you will need to complete this lab.
DEVELOPMENT ENVIRONMENT
You may use any development environment of your choice.
EXERCISE ONE (2 marks)
Recursive reverse
For this exercise you need to define a recursive function called PrintReverse() which take an
integer as input, and prints the digits in this integer in reverse order.
For example, the function call:
PrintReverse(123456);
should print:
654321
The following diagram illustrates how we can solve this problem recursively:
How should the PrintReverse() function be defined?
void PrintReverse(int n)
{
}
Base case:
A good base case for this problem will be when the input value, n, is less than 10 (i.e. a single
digit). In this case, the digit can just be printed
Recursive case:
Step 1: the expression n % 10 gives you the right-most digit which can just be printed
Step 2: the expression n / 10 gives you the number excluding the rightmost digit, which can
then be the input to the recursive function call.
EXERCISE TWO (3 marks)
Recursive conversion
For this exercise you need to define a recursive function called ConvertToBinary() which take
an integer as input and prints the binary equivalent of this input value. There is a simple algorithm for
converting a decimal number to binary:
1. repeatedly divide the number by 2
2. write down the remainder at each step
3. stop when the number reaches 0
4. the binary number is the list of remainders in reverse
For example, start with the number 157. If we repeatedly divide this by 2 and write down the
remainders:
Division Result Remainder
157/2 78 1
78/2 39 0
39/2 19 1
19/2 9 1
9/2 4 1
4/2 2 0
2/2 1 0
1/2 0 1
Now, let’s write these remainders down in reverse:
1 0 0 1 1 1 0 1
This is the binary equivalent of the decimal number 157. You could easily write a program to perform
this conversion using a loop. However, in this exercise you must write a recursive function to solve
the problem. You must not use any loops in your solution.
If you look at the previous example, let’s say you KNEW HOW TO print 78 in binary (1001110). In
that case, to print 157 in binary all you would have to do is print 78 in binary first (note, this is n / 2),
and then print 157 % 2 (in this case 1). In other words, to solve the problem of size n, the recursive
step involves solving the problem for size n / 2 and then printing n % 2. So, how should the
ConvertToBinary() function be defined?
void ConvertToBinary(int n)
{
}
Pay particular attention to the base case and the recursive case below.
To “convert n to binary”:
Base case:
if n is 1, then simply print 1
Recursive case:
otherwise, “convert n / 2 to binary” and then print n % 2
EXERCISE THREE (3 marks)
Recursive combinations
The number of combinations of m things chosen out of n is written:
m
n
and is pronounced "n choose m". For example, there are 52 cards in a deck, all distinct. The number
of possible poker hands is the number of different ways we can pick five cards from the deck:
5
52
There is an elegant recursive definition of
m
n as follows:
Base cases
0
n = 1. That is, there is only one way to pick zero things out of n: pick nothing.
n
n = 1. That is, the only way to pick n things out of n is to pick them all.
Recursive case
If 0 < m < n, then
1
11
m
n
m
n
m
n
For this exercise, you should define a function called Choose() which takes two integer inputs, n
and m, and which calculates
m
n .
How should the Choose() function be defined?
int Choose(int n, int m)
{
}
For example, the following code:
printf("Result = %d", Choose(6, 2));
should print:
Result = 15
EXERCISE FOUR (2 marks)
Time to reflect (one more time!)
Over the past few weeks, you've been learning C programming and completing many different tasks.
At the beginning of this C module, we asked you to reflect on your experience working together in
groups when you are practicing and learning programming. Now we'd like you to reflect back on how
your preferences for working in groups have changed over the course of this semester.
Questions 4 – 7 (“self-regulation”)
Like any subject, learning programming presents unique challenges. Everyone learns and studies in
their own way and now, as you begin learning a new programming language, it may be beneficial to
reflect on what strategies work best for you. “Self-regulation” of learning describes the processes
that help you understand what is working or not about your behaviour and strategies for learning.
Exercises 4-7 will help step you through this reflection.
Questions 8 – 11 (“co-regulation”)
In the ENGGEN131 course, any source code that you submit for marking should be written by
yourself, however discussing ideas at a "high-level" or talking through problems with others can be
helpful. You are encouraged to discuss course material or general problems with others, if you find
that useful. Like “self-regulation” of learning when you study by yourself, when you study in a group
or with others the term “co-regulation” of learning describes the social strategies and processes that
you use when learning together with others. Exercises 8-11 will help step you through this reflection.