Function Templates and Recursion

Function Template

Function Templates are functions written with a placeholder for return and data types so as to allow for the use of any arguments types wherever it is appropriate invoke that function with such types. We leant that if we have functions that perform similar tasks, we can use function overloading. This however requires that we have to have different data types not only in the functions definitions but also in their invocations. But where functions have the same logic and identical definitions, then there is no need to write several overloaded functions. Instead, we write one template function and the compiler writes for us a specialized function for any function call we make using data types of our choosing.

A template function is written by preceding the function declaration with a key word<template followed with a template parameter list enclosed in the angle brackets(< >). A template parameter list includes the key a type-name or class ( the two are used interchangeably) followed by a a formal type parameter. The formal type parameter is a type place holder which the compiler substitutes with the types of the arguments in the function call. A function declaration is then done as usual but with a formal type parameter placed in places where type declarations are made.

#include<iostream>

using namespace std;
// Use template key word indicates to the compiler
//that the function is a template. T is a type place holder
template <class T>
T Double(T b, T c) //Note that the both return and
//data types are declared with the place holder T
{
return b*c;
}
int main()
{
int width =4, height=5;
cout<<"Using type int arguments, the compiler substitutes T with int "
<< " and we get the area of a rectangle as "<<Double(width,height)<<" centimeters "<<endl;

double wid =4.5, heit=5.0;

cout<<" Using type double arguments, the compiler substitutes T with double " <<"and we get the area of a rectangle as
"<<Double(wid,heit)/2<<" centimeters "<<endl;

return 0;
}

The area of a rectangle is 20 centimeters

The area of a triangle is 11.25 centimeters

Given the arguments types (int and double) we provided in the example above, the compiler automatically generates two different function template specialization to handle each type of call appropriately

Recursive Fucntion

A recursive function is a function that that calls itself directly in directly through another function. A function requires to know the end point (also known as the base case) upon which it returns a result. The functions we have used so far have retuned results interactively meaning that they had specific base cases upon which to return the results. But sometimes this base case is not so direct and the function may require more and more related operations on the problem before it can return a value.

To avoid having to call other functions do related operations on the same problem, we make a function call itself repetitively until it has the final result to return. Initially the function splits the problem into two results. One where the operations are complete and another which requires further operations. Through successive calls to itself, the function continues to split the later part of the problem in the same way until it reaches the final part (base case) where no further operations are necessary. With the base case, the function begins successive returns again to itself and when it is ready a final result is returned to the original caller. Below we will use the recursive function to solve for us a factorial problem.

A factorial of a number is a product of all the numbers from one to that number. So 3 factorial written as 3!=3*2*1. The factorial of one (1!) and zero(0!) is one. Also important to note is that the factorial of a number is that number times the factorial the same number less one, i.e. 3!=3*(3-1)!. In other words n!=n*(n-1)!

So bearing in mind that 1!=1 and n!=n*(n-1), we can write our recursive function as follows;

#include<iostream>

using namespace std;
signed int fuct(int n)
{
if (n<=1)//the base case
return 1;
return n*fuct(n-1); // note function fuct() calls itself
}
int main()
{
cout<<"5! is the same as 5 x 4 x 3 x 2 x 1 = "<<fuct(5);
return 0;
}

5! is the same as 5 x 4 x 3 x 2 x 1 = 120

Note that in the above example we first determined the base case to be n=1. This is important because the function has to know when stop recursion calls. Failure to include the function can continue with recursive calls indefinitely. This consumes memory. We also separated the problem into two, n which is the simplest and final form and the n-1 which requires further operations. So for every recursion the function split further the problem as follows

The first attempt result in 5*(5-1)!, the second will have 4*(4-1)!, the third will be 3*(3-1)!, the fourth 2*(2-1)! and the last has 1*(1-1)!. When the function reaches the (1-1)!=0!=1 it will notice the base case and then each answer beginning with the last recursion will be returned to the to caller until the first call (5*(5-1)!)=120. This final result is then returned to the original caller.

Because the recursive function calls tend to grow bigger, it is important to use the data that can handle such data values. Imagine you are getting a factorial of 10,000, you will need a very large data type to handle such a figure. In our case we used signed int but this can be very small where n is also large. Signed double can be used although this also has a limit. Where necessary use large data C++ capabilities (which will cover later) where you feel you need to handle values bigger than what signed double can handle.

PREV: Default arguments and functions