Let us write a program that reads real numbers `a`

, `b`

, `c`

, and ` d`

from user input and evaluates
\[(a^2+7a+5)+(b^2+7b+5)+(c^2+7c+5)+(d^2+7d+5).\]
One possible solution is

#include<iostream> int main(){ double a,b,c,d; std::cin>>a>>b>>c>>d; double result=a*a+7*a+5; result = result + b*b+7*b+5; result = result + c*c+7*c+5; result = result + d*d+7*d+5; std::cout<<result<<"\n"; return 0; }

We have written very similar code \(4\) times. This writing style is not elegant. It is difficult to maintain non-elegant programs. If an error is discovered, then we would have to correct the error in four different places. Also, in the future we may find an improvement, such as the following identity \[a^2+7a+5=a\cdot(a+7)+5.\] We may decide to use it to improve our code. This identity would indeed make the program faster because multiplication is much slower operation than addition, so avoiding one of the multiplications will actually improve the code. Again, this improvement would have to be included in 4 different places.

Most of the programming languages let us write functions. Functions can be later called from various parts of the program. We will write the functions before the line `int main()`

.

This is how the program from above can be improved if we add one function:

#include<iostream> double myQuadraticFunction(double x){ double r = x*x+7*x+5; return r; } int main(){ double a,b,c,d; std::cin>>a>>b>>c>>d; double result=myQuadraticFunction(a); result = result + myQuadraticFunction(b); result = result + myQuadraticFunction(c); result = result + myQuadraticFunction(d); std::cout<<result<<"\n"; return 0; }

It will takes us a while to learn all the powerful features of functions in C++. We will continue learning about functions in later chapters of these lecture notes. Our goal for now is just to cover the most basic properties that will suffice to start solving fun problems.

Let us start with the analysis of the first line: The text `double myQuadraticFunction(double x)`

is called *declaration* of the function. The code that follows is called *implementation*. Declaration starts with a word such as `double`

, `long`

, or `std::string`

that identifies the type of the return value of the function. The next word is the name. We chose the name to be `myQuadraticFunction`

. Then in brackets we list the *arguments*. Before each argument we must specify its type.

The function `max3`

has to calculate the maximum of the three arguments `a`

, `b`

, and `c`

of type double.
The implementation is missing some commands.
Replace the text `// ??? //`

with the missing commands that would result in the correct function.

#include<iostream> double max3(double a, double b, double c){ double result; result = a; if(b > a){ result =b; } // ??? // return result; } int main(){ double x; double y; double z; std::cin>>x>>y>>z; double m=max3(x,y,z); std::cout<<m<<"\n"; return 0; }

The function `frog`

should take two arguments `a`

and `b`

of type `long`

and calculate

max{a,b}+a*b.Replace the text

`// ??? //`

with the missing commands that would result in the correct function.
#include<iostream> long frog(long a, long b){ long result; result = a; if(b > a){ result =b; } // ??? // return result; } int main(){ long x; long y; std::cin>>x>>y; double f=frog(x,y); std::cout<<f<<"\n"; return 0; }

The user input consists of a sequence of positive integers \(x_0\), \(y_0\), \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(\dots\) We do not know the length in advance. A negative number or \(0\) instead of a value for \(y_n\) is the signal that the input is over. Create the program that calculates

\[\left(\max\left\{x_0,y_0\right\}+x_0y_0\right)+\left(\max\left\{x_1,y_1\right\}+x_1y_1\right)+\cdots+ \left(\max\left\{x_{n-1},y_{n-1}\right\}+x_{n-1}y_{n-1}\right).\]#include<iostream> int alpha(int x){ int z; z=x+3; return z; } int beta(int x){ int z; z=2*x+5; return z; } int main(){ int w=7; int r=alpha(w)+alpha(beta(w+2)); std::cout<< r << "\n"; return 0; }

The function that makes a call to itself is called *recursive function* or *recursion*.
We will start with very simple problems. These introductory problems will be easier to solve without recursion. However, please read the text, even if you see simple solutions. The technique of building recursive functions is quite tricky. The next few very simple problems will allow us to make clear explanations.

Our first problems is this: Create a function `sumOfConsecutiveNumbers`

whose input is a positive integer \(n\) and the output is the sum of all integers from \(1\) to \(n\). Therefore, the output of the function should be \[1+2+\cdots+n.\]

We know that the above sum is equal to \(\frac{n(n+1)}2\). We will pretend that we don't know the answer. We want to solve this problem by making a C++ function that calls itself.

Assume that adding the numbers from \(1\) to \(n\) is difficult. Our approach starts with imagining the following two things:

**First thing to imagine:**You are a Boss who is given the number \(n\) and asked to calculate \(1+2+\cdots +n\).**Second thing to imagine:**You are allowed to hire an employee, or several employees. You are allowed to give employees very difficult problems. There is only one requirement: Each employee must get an**easier**problem from the one that you got!

In this case the boss can hire one employee. The boss will ask the employee to add the numbers from \(1\) to \(n-1\). Adding the numbers from \(1\) to \(n-1\) is easier than adding the numbers from \(1\) to \(n\). The employee will calculate the sum and give the result to the boss.

Let us denote by \(E\) the result that the employee obtained. Let us denote by \(B\) the result that the boss needs to calculate. Once the boss receives the answer \(E\), the boss can easily obtain the number \(B\) using the equation \[B=E+n.\]

The employee will use exactly the same algorithm. The employee will hire someone else, *employee of the employee*. The *employee of the employee* will also hire someone else, and we must make sure that this does not turn into an infinite hiring game. Computers are pretty bad with dealing with infinity. They are good with huge numbers. But when huge becomes infinity, then the computers are bad.

Therefore, some employee will not be allowed to hire the employee of their own. The employee who receives very small \(n\) will not be allowed to receive help. If the function receives \(0\) as the value for \(n\), then the function should return \(0\). Here is the entire program

#include<iostream> long sumOfConsecutiveNumbers(long n){ if(n==0){ return 0;} long B,E; E = sumOfConsecutiveNumbers(n-1); B = E + n; return B; } int main(){ long n; std::cin>>n; std::cout<<sumOfConsecutiveNumbers(n)<<"\n"; return 0; }

*Remark:* A function is allowed to have multiple return statements. Once the program encounters a return statement, the execution stops. In the case of our function, if the value of `n`

is 0, then the program will execute the statement `return 0;`

. At that point, the program exits the function.
Although we are allowed to put return statements anywhere in the function, it is considered a bad practice to do so excessively. The use of return statements should be limited to places where they are easy to spot by people who will in future maintain and debug the program. That means the return statements should be only in the end of the function, or in the very beginning when we are treating the most simple or trivial cases of input values. We are then allowed to exit the function and return the obvious results for trivial inputs, instead of performing the lengthy procedures that the function contains.

Let us look at an example of the execution of the function for \(n=3\).

**Example: \(n=3\).** In this example, the Boss receives the value \(3\) as the argument of the function.

**Function executed by the Boss.**The boss receives the argument`n=3`

and declares the variables`B`

and`E`

. We will call these variables`n0`

,`B0`

, and`E0`

. The Boss then hires an employee. Let us use the name`Employee One`

to denote this employee. The boss will ask Employee One to execute the same function, but with different argument. The value of the argument`n`

will be`3-1=2`

. The Boss will receive the result`E0`

from Employee One. The boss will calculate`E0+3`

and obtain the result`B0`

. This is how we will summarize these data:n0=3; E0 = sumOfConsecutiveNumbers(2); B0 = E0 + 3;

**Function executed by Employee One.**Employee One will be the boss of his/her own. Employee One will receive the argument`n`

with the value \(2\). Employee One will declare the variables`B`

and`E`

. We will call these variables`n1`

,`B1`

, and`E1`

. The value`E1`

will be calculated by another employee hired by Employee One. Let us give the name`Employee Two`

to the person hired by Employee One. The person`Employee Two`

will receive the value`2-1=1`

as the content of the argument`n`

. Employee One will then add the number`n1`

, which is`2`

, to the number`E1`

and return the result to the Boss. This is the summary of the job performed by Employee One.n1=2; E1 = sumOfConsecutiveNumbers(1); B1 = E1 + 2;

**Function executed by Employee Two.**The logic is analogous to the previous cases. We will denote the argument by`n2`

and the local variables by`B2`

and`E2`

. The variable`E2`

will be evaluated by an employee of Employee Two. This person will be called`Employee Three`

. The summary of the job performed by Employee Two is:n2=1; E2 = sumOfConsecutiveNumbers(0); B2 = E2 + 1;

**Function executed by Employee Three.**This employee will not hire anyone. Because the content of the argument is \(0\), Employee Three returns the value 0. Hence, the summary of the job of Employee 3 is:return 0;

Therefore, `Employee Two`

receives 0 and stores the value `0`

inside `E2`

. `Employee Two`

then evaluates `B2`

and obtains `1`

. `Employee Two`

returns the value 1 to `Employee One`

. `Employee One`

then has `E1=1`

and evaluates `B2=E1+2=3`

. The value 3 is return to `Boss`

who updates `E0=3`

. Then, Boss evaluates `B0=E0+3=6`

. Boss returns the value 6.

We will create a recursive function that determines the element \(f_n\) of the sequence defined by \(f_0=0\), \(f_1=1\), and \[f_{n}=5f_{n-1}-6f_{n-2},\quad\mbox{for }n\geq 2.\] The element \(f_2\) is \(f_2=5f_1-6f_0=5\cdot 1- 6\cdot 0=5\).

We will solve this problem using recursion. We will create the function `f`

with argument `n`

of type `long`

that evaluates the term \(f_n\) of the sequence.

We will assume that we are the Boss. We receive the number `n`

and we have to calculate `f(n)`

. We will first check whether `n`

is `0`

or `1`

. In the case `n==0`

we return `0`

. In the case `n==1`

, we return `1`

. In every other case, the Boss will hire two employees `Employee One`

and `Employee Two`

. The boss will use two variables `E1`

and `E2`

. The variable `E1`

will be the result of the evaluation of the function by our Employee One who receives `n-1`

as the argument. The value `E2`

will be the result of the evaluation of the function by Employee Two who will receive `n-2`

as the argument. Then the boss will return `5*E1-6*E2`

. The complete code is given below.

#include<iostream> long f(long n){ if(n==0){return 0;} if(n==1){return 1;} long E1=f(n-1); long E2=f(n-2); return 5*E1-6*E2; } int main(){ long n; std::cin>>n; std::cout<<f(n)<<"\n"; return 0; }

A sequence is called *lucky* if the numbers \(1\) and \(3\) are never adjacent and in this order. The user input consists of a positive integer \(n\). Create the program that counts the number of lucky sequences of length \(n\) whose terms are \(1\), \(2\), and \(3\).

For example, when \(n=3\), the number of lucky sequences is \(21\). The sequences are \begin{eqnarray*} &&111, \; 112,\; 121,\; 122,\; 123,\; 211,\; 212,\; 221,\; 222,\; 223,\;231,\;\\ &&232,\; 233,\; 311,\; 312,\; 321,\; 322, \; 323,\; 331,\; 332,\; 333 \end{eqnarray*}

Create an implementation of the function `f`

that for given integer `n`

evaluates the term \(f_n\) of the sequence given by \(f_0=0\), \(f_1=2\), \(f_2=3\), and \[f_{n+3}=f_{n+2}+f_{n+1}+2f_{n},\quad\mbox{for}\quad n\geq 0.\]
Write the code that replaces the text `// ??? //`

below.

long f(long n){ if(n==0){return 0;} if(n==1){return 2;} if(n==2){return 3;} // ??? // }

Create a recursive function that sums the digits of the positive integer \(n\).
Write the code that replaces the text `// ??? //`

below.

long sumDigits(long n){ if(n==0){ return 0; } // ??? // }

For a given positive integer \(n\), determine the number of sequences of length \(n\) whose terms are from the set \(\{1,2,3\}\) in which \(1\) and \(3\) are never next to each other (both \(31\) and \(13\) must be avoided).

For example, when \(n=3\), the number of sequences is \(17\). The sequences are \begin{eqnarray*} &&111, \; 112,\; 121,\; 122,\; 123,\; 211,\; 212,\; 221,\; 222,\; 223,\;\\ &&232,\; 233,\; 321,\; 322, \; 323,\; 332,\; 333 \end{eqnarray*}

The user input consists of two positive integers \(X\) and \(N\). Determine the number of ways in which \(X\) can be written as the sum of perfect \(N\)-th powers of distinct positive integers.

Example 1:

Input: 200 2 Output: 9

Explanation: There are nine ways in which \(200\) can be written as the sum of perfect squares. They are \begin{eqnarray*} 200&=&1^2+2^2+3^2+4^2+5^2+8^2+9^2, \\200&=&1^2+2^2+3^2+4^2+7^2+11^2, \\200&=&1^2+2^2+5^2+7^2+11^2, \\200&=&1^2+3^2+4^2+5^2+6^2+7^2+8^2, \\200&=&1^2+3^2+4^2+5^2+7^2+10^2, \\200&=&2^2+4^2+6^2+12^2, \\200&=&2^2+14^2, \\200&=&3^2+5^2+6^2+7+9^2, \quad\mbox{and} \\200&=&6^2+ 8^2+10^2. \end{eqnarray*}

Example 2:

Input: 1008 3 Output: 2

Explanation: There are two ways in which \(1008\) can be written as the sum of perfect cubes. They are \begin{eqnarray*} 1008&=&1^3+3^3+5^3+7^3+8^3\quad\mbox{and}\\ 1008&=&2^3+10^3. \end{eqnarray*}

The user input consists of positive integers followed by a single non-pozitive integer that signals the end of the input. The total size of the input gives remainder \(1\) when divided by \(10\). There is one integer that appears exactly \(11\) times among the input values. Every other integer appears either \(0\) times or \(10\) times. Create a program that finds out the integer that appears \(11\) times.

Example input:

107 107 107 795 882 882 795 795 107 107 795 882 882 882 882 107 795 107 107 795 795 795 795 882 795 882 882 107 795 107 882 -9The output of the program should be

`795`

.