The square function
Complete the function square, which returns the square of its argument. main reads n and prints square(n).
525A C/C++ program is a collection of distinct modules called functions. Splitting the code into small functions, each with a clear responsibility, is the main tool for controlling complexity: it makes the code reusable, testable, and much easier to read.
return_type function_name (parameter_list)
{
<local declarations>
sequence of statements
}
| Element | Role | Notes |
|---|---|---|
return_type | the type of the returned value | defaults to int; write void if nothing is returned |
function_name | identifier | follows identifier rules |
parameter_list | declarations of the form type name | separated by commas; void or empty if there are none |
// PROTOTYPE (declaration) - tells the compiler what to expect
double area(double radius); // placed before main, in the global zone
int main(void) {
printf("%.2f\n", area(2.5)); // the call is now valid
return 0;
}
// DEFINITION - the actual body, can also be in another file
double area(double radius) {
return 3.14159 * radius * radius;
}
| Mode | What the function receives | Modifies the original? | Cost |
|---|---|---|---|
| By value | a copy of the value | no | copying the data |
| By pointer | the address of the variable | yes | just an address |
| By reference (C++) | an alias of the variable | yes | just an address |
| Array | always the address of the first element | yes | just an address |
int v[], the function receives a pointer, so changes are
reflected in the original array. For the same reason, sizeof applied to the
parameter gives the size of a pointer, not of the array - the size must be passed separately.Watch what happens to variables when a function is called: copies are created on the stack, and they disappear on return. Observe why the first version modifies nothing.
| Variable type | Visible in | Lives |
|---|---|---|
| Local (automatic) | the block where it is declared | until exiting the block |
| Formal parameter | the function body | for the duration of the call |
Local static | the block where it is declared | the whole program |
| Global | the whole file, after the declaration | the whole program |
::name.A recursive function calls itself. Any recursive function must have:
| Problem | Recursive | Iterative |
|---|---|---|
| Factorial | elegant, but uses stack space | more efficient |
| Naive Fibonacci | very slow - O(2^n), recomputes the same values | O(n) |
| Tree traversal | natural and clear | needs an explicit stack |
| Towers of Hanoi | the obvious solution | complicated |
| Facility | Description | Example |
|---|---|---|
| Overloading | several functions with the same name, but different parameters | int max(int,int) and double max(double,double) |
| Default parameters | values used if the argument is missing at the call | void f(int a, int b = 10) |
inline functions | the code is inserted at the call site | inline int square(int x) |
| References | passing without copying, with simple syntax | void f(int &x) |
#include <stdio.h>
// prototypes
double area(double radius);
int maximum(int a, int b);
void printLine(char c, int n);
void minMax(int v[], int n, int *min, int *max);
int main(void)
{
printLine('=', 40);
printf("Area for r=2.5: %.4f\n", area(2.5));
printf("Maximum of 17 and 42: %d\n", maximum(17, 42));
int v[] = {29, 10, 14, 37, 5};
int mn, mx;
minMax(v, 5, &mn, &mx); // two results through pointers
printf("Minimum=%d Maximum=%d\n", mn, mx);
printLine('=', 40);
return 0;
}
double area(double radius) { return 3.14159265 * radius * radius; }
int maximum(int a, int b) { return (a > b) ? a : b; }
void printLine(char c, int n)
{
for (int i = 0; i < n; i++) putchar(c);
putchar('\n');
}
void minMax(int v[], int n, int *min, int *max)
{
*min = *max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < *min) *min = v[i];
if (v[i] > *max) *max = v[i];
}
}
#include <stdio.h>
long factorialRec(int n)
{
if (n <= 1) return 1; // BASE CASE - mandatory
return n * factorialRec(n - 1); // recursive step
}
long factorialIter(int n)
{
long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
long fibonacciRec(int n) // WARNING: exponentially slow
{
if (n <= 1) return n;
return fibonacciRec(n - 1) + fibonacciRec(n - 2);
}
long fibonacciIter(int n) // linear, much faster
{
long a = 0, b = 1, t;
for (int i = 0; i < n; i++) { t = a + b; a = b; b = t; }
return a;
}
int gcd(int a, int b) // Euclid's algorithm
{
if (b == 0) return a;
return gcd(b, a % b);
}
int main(void)
{
printf("10! recursive = %ld\n", factorialRec(10));
printf("10! iterative = %ld\n", factorialIter(10));
printf("Fibonacci(20) = %ld\n", fibonacciIter(20));
printf("gcd(48, 18) = %d\n", gcd(48, 18));
return 0;
}
#include <iostream>
using namespace std;
// same name, different parameters
int maximum(int a, int b) { return (a > b) ? a : b; }
double maximum(double a, double b) { return (a > b) ? a : b; }
int maximum(int a, int b, int c) { return maximum(maximum(a, b), c); }
// default parameters - only at the end of the list
void print(const char *text, int repeats = 1, char separator = '\n')
{
for (int i = 0; i < repeats; i++)
cout << text << separator;
}
// passing by reference
void doubleIt(int &x) { x *= 2; }
int main()
{
cout << maximum(3, 7) << endl; // int version
cout << maximum(3.5, 7.1) << endl; // double version
cout << maximum(3, 7, 5) << endl; // three-parameter version
print("Hello"); // uses the default values
print("Test", 3); // repeats 3 times
print("A", 4, ' '); // custom separator
cout << endl;
int n = 21;
doubleIt(n);
cout << "n = " << n << endl; // 42
return 0;
}
For functions, the panel on the right shows the call stack: each call has its own set of variables. With recursion you can see the frames piling up one on top of another.
factorial() frames are shown stacked on top of each other: each has its own
n. Delete the stopping condition and you will see a stack-overflow error.This is where you write the code. The ✓ Check button runs your program on several data sets and shows you right away where the result differs. At the end you submit the track you chose, and the instructor grades it automatically.
Every exercise has the program already started, and the comments tell you what is left to add. Write the code, press ✓ Check and read what each failed test says. If you get stuck, open the hints one at a time. You may also print messages for the user (such as Enter n:); the test looks at what you print at the end.
Complete the function square, which returns the square of its argument. main reads n and prints square(n).
525Complete the function fact, which computes n! (0 ≤ n ≤ 20) iteratively, in a long long.
5120Complete the function is_prime, which returns 1 if n is prime and 0 otherwise. main prints prime or nonprime.
7primeComplete the recursive function digit_sum, without loops: the digit sum of n is the last digit plus the digit sum of n / 10.
123410Complete the recursive function gcd using Euclid's algorithm: gcd(a, 0) = a and gcd(a, b) = gcd(b, a % b).
48 186Problems start from an empty main. The output format must be followed exactly (spaces and newlines do not matter unless the statement says otherwise), so do not print prompts. The visible tests cover only the simple cases; grading also runs hidden tests chosen to catch the edge cases.
Read n (0 ≤ n ≤ 90) and print F(n), where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). The tests include large values of n, so the direct recursive version will not finish in time.
1055Read a b m (0 ≤ a ≤ 109, 0 ≤ b ≤ 1015, 1 ≤ m ≤ 9·107). Print ab mod m. With b this large you need a logarithmic algorithm.
2 10 100024Read n (1 ≤ n ≤ 10). Print the moves that take n discs from peg 1 to peg 3, one per line, in the form 1 -> 3, then the total number of moves.
21 -> 2
1 -> 3
2 -> 3
3Read n (1 ≤ n ≤ 6) and print every permutation of {1, …, n}, in lexicographic order, one per line (numbers separated by spaces).
31 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1sizeof inside it - explain the result.