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. Alright, let’s get started... EngGen 131 S2 2021 Lab 12 – 2 – Course Manual (C Programming) 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. EngGen 131 S2 2021 Lab 12 – 3 – Course Manual (C Programming) 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 EngGen 131 S2 2021 Lab 12 – 4 – Course Manual (C Programming) 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 EngGen 131 S2 2021 Lab 12 – 5 – Course Manual (C Programming) 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.
欢迎咨询51作业君
