ESc 014

Lab 5 -- Recursion
Thursday, May 9, 2002


Your Mission

In this lab, you are to write a program that will compute the sum of the first n integers, where n is a number that the user will enter. For example, if the user enters the number 5, the program will display the sum of 1 + 2 + 3 + 4 + 5, or 15.

The Details

Your main function will ask the user to enter a positive integer. You should re-prompt for input if the user does not enter something positive and continue to re-prompt until a positive number is entered. Your program should then call a recursive function named sumOfInts that will take the user's integer (call it n) as a parameter. sumOfInts will return the sum of 1+2+...+n so that it can be printed by the main function.

Your sumOfInts function should not use loops (for, while, do-while) to compute the sum. It should use recursion. It should also be able to do it without using an array. Debug your code until it works.

Think Recursively

Recursion is a tough concept. The trick to writing a recursive solution is to first think about the two things every recursive function needs:
  1. A recursive case: this is where you need to state the problem in terms of a smaller version of itself. For this problem, you can think of it like this: the sum of the first 8 integers (i.e. if the user entered 8) is equal to 8 + the sum of the first 7 integers. In general, the sum of the first n integers is equal to n + the sum of the first n-1 integers.
  2. A base case: this defines how the function will stop recursing. It usually corresponds to a "trivial" case of the problem -- one whose solution is obvious. What would be the base case here? That is, what would be the trivial n that the user could input whose solution is obvious?

How to turn in this lab

Remember, you will be graded on the correctness of your implementation, neatness, presentation, style of your program code, thoroughness of your testing, and good use of the C++ language. It's important to comment your code where appropriate and to do little things like space things properly, use readable indentation, and also to make sure the overall design and logic of the program are coherent.

Turn in a hard copy of your source code along with your test results appended at the bottom as a comment. Then turn in the source code electronically on BlackBoard.

Return to Lab Index