Functions and Recursions

1. Functions

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.

Problem 1.

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;
}

Problem 2.

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;
}

Problem 3.

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).\]

Problem 4. What happens when the following code is executed?
#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;
}

2. Recursive function

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.

2.1 Recursive function that adds the integers from \(1\) to \(n\)

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.

2.2 Recursive function that calculates terms of a sequence

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;
}

2.3 Counting sequences

Problem 5.

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*}

2.4 Practice problems

Problem 6.

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;}
   // ??? //
} 

Problem 7.

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;
  }
  // ??? //
} 

Problem 8.

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*}

Problem 9.

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*}

Problem 10.

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 -9
The output of the program should be 795.