Learning programming and learning programming language are not the same. Most of our textbooks teach us programming languages. In truth, a programming language is just a tool that we use to implement an executable program. We need resources that teach us how to solve problems using a programming language.
As early as elementary school, we learned what is a mathematical function and how to write it. For example, f(x)=x^2
is a simple quadratic function.
A function describes a mathematical statement. The above function maps the relationship between two sets of natural numbers as given at the right in the graph below. Often, it is impossible to show such a mapping graphically when we have a large number of discrete elements in either of the sets. Therefore, for convenience, we express a function by writing it as an inherent relation between the sets.
This is perhaps the simplest way to demonstrate relationships when we deal with sets of numbers (integer, natural number, real numbers, complex numbers, etc.)
We can also think of a function as a machine which has taken in inputs and produces an output by using a mechanism that maps the relationship from input to output. The sets to which the inputs and output belong are also important. A function often has a name that allows us to identify it. Typically a function is deterministic, it can produce only a single output from a unique set of inputs.
Using different mathematical strategies, we can solve problems under various domains.
One philosophical foundation of computer programming was to represent or express all kinds of mathematical problems by a single language and solve them using generalized mathematics. The result was two equivalent systems, the Turing machine and lambda calculus.
The concept of a Turing machine influenced imperative programming paradigm such as those of Assembly, C, C++, Java, Ruby, Python, and other programming languages.
On the other hand, lambda calculus influenced the birth of several functional languages such as LISP, ML, Haskell, and Erlang.
Although we can solve many more problems by using those programming languages than by using high school math, it is often easy to learn programming by solving smaller problems first. In this book (or booklet), we will learn how to solve a problem of known category. In the beginning, we will see how a simple arithmetic function can be converted into a computer program. Later, we will learn to convert more complex functions. We will also learn how to compose a function using other functions. A function can also be built using itself through recursion. We will see how they can be converted using usual pattern matching.
Rather than learning alien text, we will try to use our common sense, simple IQ and pattern matching to convert a mathematical function into a computer program. Although we will write all the code in the language C, any other language can be used instead. If we use other languages, we may need to transform the given programs to that target language. So, if we do not know any other language, it is better to stick to C.
Anyway, instead of coding (writing in a computer to execute it physically) the converted code in this book, we will try to learn the programs by jotting it down independently. Initially, most problems given here are small and easy to write on a notebook (paper) by pen or pencil. In this way, the learner becomes familiar with the relationship between theoretical formulas and the implemented programs.
We will convert some basic functions into programs in this section. First, we will see how to write programs for unary functions. Later, we will learn the same of binary and n-ary function.
The identity function (or a function in which output mirrors the input) looks like this:
Function id(x) = x
can be converted into:
1int id(int x){
2 return x;
3}
Successor functions use the +
operator to add 1
to the input and return its successor.
Operator | Name |
---|---|
+ | Addition |
- | Subtraction |
* | Multiplication |
/ | Division |
% | Reminder |
Function suc(x) = x + 1
can be converted to:
1int suc(int x){
2 return x + 1;
3}
This is defined as twice(x) = 2x
in arithmetic.
In C, the same function takes the form below.
1int twice(int x){
2 return 2 * x;
3}
This function is defined as square(x) = x^2
arithmetically.
In C, it takes the form below.
1int square(int x){
2 return x * x;
3}
Here we present a pictorial representation of the above function square where the parameter x
is mutiplied with itself to produce and return the result.
In arithmetic, the function is defined as: poly_1(x) = x^2 + 1
It can be converted into a programming function as shown below:
1int poly1(int x){
2 return x * x + 1;
3}
In arithmetic, the function is defined as: poly2(x) = x^4 + x^2 + 1
It can be converted into a programming function as shown below:
1int poly2(int x){
2 return (x * x * x * x) + (x * x) + 1;
3}
This can be simplified:
1sum_{i=1}^ni = n(n+1)/2
It can be converted into a programming function as:
1int sum(int n){
2 return n * (n + 1) / 2;
3}
Convert the arithmetic functions into programming function:
f1(x) = x + 2$ $f2(x) = x^3$ $f3(x) = 2x^2 + 3
f4(x) = 3x^3 + 4x^2 + 7$ $_1(m) = m(m+1)(2m+1)/6
sumOfSquare_2(m) = m^3/3 + m^2/2 + m/6$ $_1(m) = (m(m+1)/2)^2
sumOfSquare_2(m) = m^4/4+m^3/2+m^2/4
(y) = y - 1
(z) = z / 2
function, such as ‘add’ in arithmetic can be defined as:
add(x, y) = x + y
It can be converted into a programming function as:
1int add(int x, int y){
2 return x + y;
3}
function in arithmetic – addSquare(x, y) = x^2 + 2xy + y^2
It can be converted into a programming function as:
1int addSquare(int x, int y){
2 return (x * x) + (2 * x * y) + (y * y);
3}
Now we will solve a problem of determining the larger number between two
numbers. In this case, we will construct a function that takes two
parameters and it will return 1
if the first parameter is larger than
the second parameter and 0
otherwise. For that we will introduce a new
operator >
.
a > b
is 1
or (True
in meaning) if a
is larger than
b
. Otherwise it is 0
(False
in meaning). So, our
function is – isLarger(x, y) = x > y
The corresponding program is:
Operator | Name |
---|---|
> | Greater than |
>= | Greater than or equal to |
< | Smaller than |
<= | Smaller than or equal to |
== | Equals to |
!= | Not equals to |
1int isLarger(int x, int y){
2 return x > y;
3}
Convert the arithmetic functions into programming function:
sub(x,y) = x - y
addOfSquare(x,y) = (x times x) + (y times y)
subOfSquare(x,y) = (x times x) - (y times y)
subOfSquare_1(x,y) = (x+y)(x-y)
g(a,b) = a + ab + b
Write functions in arithmetic and programming to – multiply two numbers. calculate average of two numbers. determine if the two given numbers are equal. determine if the two given numbers are not equal.
A ternary function takes three parameter. For example:
avgOfThree(x, y, z) = (x + y + z) / 3
It can be converted into a programming function as:
1int avgOfThree(int x, int y, int z){
2 return (x + y + z) / 3;
3}
In a n-ary function, number of parameters is n. In this example, square of distance is an useful function to compare two distances.
The squareOfDistance
function:
squareOfDistance(x_1, y_1, x_2, y_2) = (x_1-x_2)(x_1-x_2) + (y_1-y_2)(y_1-y_2)
Can be converted into a programming function as:
1int squareOfDistance(int x1, int y1, int x2, int y2){
2 return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
3}
A function can be composed using other functions. It often simplifies
the expression. For example, the function, squareOfDistance
can be
simplified if we use the function square
. It is shown here:
1square(x) = x times x
2
3squareOfDistance_1(x_1,y_1,x_2,y_2) = square(x_1-x_2)+square(y_1-y_2)
Let us write it in a programming language:
1int square(int x){
2 return x * x;
3}
4int squareOfDistance1(int x1, int y1, int x2, int y2){
5 return square(x1-x2) + square(y1-y2);
6}
Here we can see that the function squareOfDistance1 is using two copies of the function square. It is very important to understand.
Poly2
The old function was defined as Poly2(x) = x^4 + x^2 + 1
.
Now we will re-define it as Poly2_1
using the function square
:
1square(x) = x times x
2
3Poly2_1(x) = square(square(x)) + square(x) + 1
In C, we can write it as:
1int square(int x){
2 return x * x;
3}
4
5int poly21(int x){
6 return square(square(x)) + square(x) + 1;
7}
sumOfQube
The old function was defined as sumOfQube_1(x) = (x(x+1)/2)^2
.
Now we will re-define it as sumOfQube
using the function square
and
sum
:
1square(x) = x times x
2
3sum(x) = (square(x) + x) / 2
4
5sumOfQube(x) = square(sum(x))
In C, we can write it as:
1int square(int x){
2 return x * x;
3}
4
5int sum(int x){
6 return (square(x) + x) / 2;
7}
8
9int sumOfSquare(int x){
10 return square(sum(x));
11}
x^3 = x times square(x)
x^8 = square(square(square(x)))
qube_c(x) = x^3
toPower8(x) = x^8
toPower4(x) = x^4
parabola(a,b,c,x) = ax^2 + bx + c
square_p(x) = parabola(1,0,0,x)
qube_p(x) = parabola(x,0,0,x)
toPower4_p(x) = parabola(parabola(1,0,0,x),0,0,x)
and prove that toPower4_p(x) = x^4
.From this chapter, we will not write same function twice.
In a function, we may get different result based on different conditions on the parameters. For example, the function absolute negates its parameter if it is negative so that it can be turned into positive (negative of negative is positive) to produce the result. Otherwise (when parameter is already positive), it returns back the result exactly same as the parameter. Thus, the function can be written as:
1abs(x) = begin{dcases*}
2 x & when `x geq 0`
3 -x & otherwise
4 end{dcases*}
Compute based on conditions of parameters.
The general idea of a conditional function is as follows:
1f(x) = begin{dcases*}
2 e_1 & when `1^{st}` condition satisfies
3 e_2 & when `2^{nd}` condition satisfies
4 e_3 & when `3^{rd}` condition satisfies
5 dots & dots
6 e_n & otherwise
7 end{dcases*}
The corresponding code is:
1int f(int x){
2 if( 1st condition )
3 return e1;
4 else if( 2nd condition )
5 return e2;
6 else if( 3rd condition )
7 return e2;
8 ...
9 ...
10 else
11 return en;
12}
Now we will present some functions those use conditions.
1abs(x) = begin{dcases*}
2 x & when `x geq 0`
3 -x & otherwise
4 end{dcases*}
It's code:
1int abs(int x){
2 if( x >= 0 )
3 return x;
4 else
5 return -x;
6}
1filter_{LT}(x,y) = begin{dcases*}
2 x & when `x geq y`
3 0 & otherwise
4 end{dcases*}
Its code:
1int filterLT(int x, int y){
2 if( x >= y )
3 return x;
4 else
5 return 0;
6}
By composing functions, we can construct many familiar functions. Although they are not always more efficient, for obvious reason, we will do it.
Here the function abs is rewritten as:
1switcher(a,b,c,d) = begin{dcases*}
2 c & when `a geq b`
3 d & otherwise
4 end{dcases*}
5
6abs_1(x) = switcher(x, 0, x, -x)
In C:
1int switcher(int a,int b,int c,int d){
2 if(a >= b)
3 return c;
4 else
5 return d;
6}
7int abs1(int x){
8 switcher(x, 0, x, -x);
9}
Lets think a problem.
Calculate your total tuition fee due based on the condition that if your due of previous semester tuition fee is more that 1000 currency, your total fee to pay this semester will be double of previous due plus the fee of current semester. We can write a function to describe it mathematically.
1tftp(p, c)=begin{dcases*}
2 2 times p + c & when `p > 1000`
3 p + c & otherwise
4 end{dcases*}
If we use the function switcher
, we can rewrite it as:
1hbox{em tftp}_1(p, c) =
2 switcher(p, 1001, 2 times p, p) + c
or,
1hbox{em tftp}_2(p, c) =
2 switcher(p, 1001, p, 0) + p + c
In programming, the functions are:
1int switcher(int a,int b,int c,int d){
2 if(a >= b)
3 return c;
4 else
5 return d;
6}
7int tftp1(int p, int c){
8 return switcher(p, 1001, 2 * p, p) + c;
9}
10int tftp2(int p, int c){
11 return switcher(p, 1001, p, 0) + p + c;
12}
Well, the parameters p
and c
does not mean
anything. So, often it misleads us if we use meaningless names. It is
also important to be able to read them easily. We can take different
approaches to avoid confusions and increase readibility. They are shown
as the function tftp2
is rewritten as:
1/*
2tftp: tuition fee to pay
3*/
4int tftp2(int p, int c){
5 /*
6 p: previous month's due
7 c: current month's fee
8 */
9 return switcher(p, 1001, p, 0) + p + c;
10}
Or, in the best style:
1int tftp2(int previousDue, int currentFee){
2 return switcher(previousDue, 1000,
3 previousDue, 0)
4 + previousDue
5 + currentFee;
6}
Or, in a good style:
1int tftp2(int preDue, int curFee){
2 return switcher(preDue, 1001, preDue, 0)
3 + preDue + curFee;
4}
Or, we can write a word to keep it small and yet understandable:
1int tftp2(int due, int fee){
2 return switcher(due,1001,due,0)+due+fee;
3}
In this example, we will solve a problem of determining the grade letter based on the total mark in an examination. The grade distribution is given at the right side.
Range Grade | letter | In numeric |
---|---|---|
90-100 | A | 1 |
80-89 | B | 2 |
70-79 | C | 3 |
60-69 | D | 4 |
40-59 | E | 5 |
0-39, <0, >100 | F | 6 |
The function that solves the problem is:
1getGrade(mark) = begin{dcases*}
2 1 & when `mark geq 90` and `mark leq 100`
3 2 & else when `mark geq 80`
4 3 & else when `mark geq 70`
5 4 & else when `mark geq 60`
6 5 & else when `mark geq 40`
7 6 & otherwise
8 end{dcases*}
Hence, the code for the above function is:
1int getGrade(int mark){
2 if( mark >= 90 && mark <= 100)
3 return 1;
4 else if( mark >= 80 )
5 return 2;
6 else if( mark >= 70 )
7 return 3;
8 else if( mark >= 60 )
9 return 4;
10 else if( mark >= 40 )
11 return 5;
12 else
13 return 6;
14}
In the above example, the function gives us a numeric value that in our mind represents a grade. But it is often necessary to give user a direct result instead of a numerical representation. If the function can generate result with letter grades directly, it will be definitely more understandable as shown here:
1getGradeLetter(mark) = begin{dcases*}
2 hbox{'A'} & when `mark geq 90` and `mark leq 100`
3 hbox{'B'} & else when `mark geq 80`
4 hbox{'C'} & else when `mark geq 70`
5 hbox{'D'} & else when `mark geq 60`
6 hbox{'E'} & else when `mark geq 40`
7 hbox{'F'} & otherwise
8 end{dcases*}
Since the letter grades are actually letters or characters, we need to change the data type of the function to ‘char’. ‘char’ type corresponds to the characters. In other words, ‘char’ is the set of all characters or visible symbols a computer can show.
Type | Nature of Data |
---|---|
int | integer |
long | large integer |
long long | very large integer |
float | real number |
double | large real number |
char | character |
The code for the above function is:
1char getGradeLetter(int mark){
2 if( mark >= 90 && mark <= 100)
3 return 'A';
4 else if( mark >= 80 )
5 return 'B';
6 else if( mark >= 70 )
7 return 'C';
8 else if( mark >= 60 )
9 return 'D';
10 else if( mark >= 40 )
11 return 'E';
12 else
13 return 'F';
14}
In this example, we will solve a problem of getting prices of different items in an restaurant. We will determine an item by its item no. The prices for different item numbers are given at the right.
Item Item | No. | Price |
---|---|---|
Fish Curry | 1 | 60.00 |
Fish Fry | 2 | 80.00 |
Beef Curry | 3 | 100.50 |
Beef Vuna | 4 | 130.75 |
Chicken | 5 | 85.00 |
Rice | 6 | 15.25 |
Water | 7 | 20.00 |
Cold Drinks | 8 | 15.00 |
The function that solves the problem is:
1{hbox{em getPrice}}({hbox{em item}}) = begin{dcases*}
2 60.00 & when {em item} `= 1`
3 80.00 & when {em item} `= 2`
4 100.50 & when {em item} `= 3`
5 130.75 & when {em item} `= 4`
6 85.00 & when {em item} `= 5`
7 15.25 & when {em item} `= 6`
8 20.00 & when {em item} `= 7`
9 15.00 & when {em item} `= 8`
10 0 & otherwise
11 end{dcases*}
Hence, the code for the above function is:
1float getPrice(int item){
2 switch( item ){
3 case 1:
4 return 60.00;
5 case 2:
6 return 80.00;
7 case 3:
8 return 100.50;
9 case 4:
10 return 130.25;
11 case 5:
12 return 85.00;
13 case 6:
14 return 15.25;
15 case 7:
16 return 20.00;
17 case 8:
18 return 15.00;
19 default:
20 return 0;
21 }
22}
Type | Range |
---|---|
int/long | -2^{31} to 2^{31} - 1 |
long long | -2^{63} to 2^{63} - 1 |
float | 1.2E-38 to 3.4E+38 |
double | 2.3E-308 to 1.7E+308 |
long double | 3.4E-4932 to 1.1E+4932 |
char | -128 to 127 |
Note: 2^{31}=2,147,483,648
and 2^{63}=9,223,372,036,854,775,808
For a realistic approach, we can add a simple function with it that calculates total price of an item for a quantity:
1calcTotalPrice(item, quantity) = quantity times getPrice(item)
The code:
1float calcTotalPrice(int item, int quantity){
2 return quantity * getPrice( item );
3}
Recursion is a technique that enhances capabilities of programs very
much. For example, if we want to write an exponential function
exp(x,k)=x^k
, we understand that x
have to be multiplied to itself
k
times. We can understand x^k
operation from our childhood
mathematics. But unfortunately C programming language does not have
operator for exponential operation. We can also understand k
times and
we can repeat this multiplication by counting 1
to k
.
But how to write the function using multiplication only? We can write
exp(x,k)=x times x times dots times x
(k
times). If we knew k
is 2
, the expression becomes exp(x,2) = x times x
, if it is 3
,
the expression is exp(x, 3) = x times x times x
and so on. But when
k
is unknown, then it is difficult to write in very clear way. Most
importantly, C programming does not support any expression like
‘x times x times dots times x
(k
times)’.
We use recursion to express such functions or programs. Recursion is a special kinds of composition where the definable function itself is composed with something else to define itself. It may heard weird or twisted at the first time. We will see some analogous definition in our society to understand its power.
But just imagine a simple definition of human (according to Quran and Bible):
‘Adam and Eve were human and any living mammal that borns from another human is a > human’.
This definition certainly covers all the humans. Here human is defined from the definition of another human and it is called recursion or induction. In recursive (or inductive) defintion, there must be at least one base point for example ‘Adam was human and Eve was human’.
Let us take another example, the definition of natural numbers. Suppose we
have all kinds of numbers on our knowledge including real numbers,
complex numbers, etc.. We need to define natural number. Here is the
plain definition - 0
is a natural number and n+1
is a natural number
if n
is a natural number. We can use it to write a function to know
whether a number is natural
1{hbox{em isNatural}}(x)=begin{dcases*}
2 {hbox{em true}}& when `x=0`
3 {hbox{em false}}& when `x<0`
4 {hbox{em isNatural}}(x-1) & otherwise
5 end{dcases*}
Similarly we can write another function to distinguish an animal as human:
1{hbox{em isHuman}}(x)=begin{dcases*}
2 {hbox{em true}}& when `x=` {em Adam}
3 {hbox{em true}}& when `x=` {em Eve}
4 {hbox{em false}}& when `x=` {em Amoeba}
5 {hbox{em isHuman}}({hbox{em mother of }}x) & otherwise
6 end{dcases*}
It says, x
is a human if x
is Adam or
Eve. x
is not human if x
is Amiba.
Besides x
is also human if and only if mother of x
is also human.
Well, in the real process, to justify an animal as human, we need to
know the total family tree from Adam and
Eve which is very unrealistic. But the definition itself
is very intuitive.
In mathematics and computer science, this recursive style of definition often expresses a fact in a very simple and intuitive way, which helps to formalize an algorithm or program in very effective way.
To create a recursive definition of a function, we need to forget how it really works. We simply need to know if the definition is correct mathematically.
For an easy construction of the definition, here we would like to present a tips. We have to remember that the function has one (or more) driving parameter(s).
Base cases part
Need to determine the value of the function for the base case(s) of
the driving parameter(s). For example, exp(n,x)=1
when x=0
.
Recursion part
The function itself will be appeared with smaller (typically
1 step) value or size of the driving parameter(s). For example,
exp(x-1)
. This is called induction hypothesis (HI).
The induction hypothesis often needs to be computed with
something else to be equal to the original definition. For
example, exp(x)=x times exp(x-1)
.
If we follow the above steps, it will help us to construct recursive definition. We will explore some examples soon. In some examples, we will see how the function is constructed from the above tips. We will also see whether definition is correct.
We will define exp(x,k)
. Here x
is the base and k
is the power. So,
k
is the driving parameter. Now we know the base case when k=0
-
exp(x,0) = 1
. Next, we will have to construct the recursion part. First, we
know that the expression exp(x,k-1)
exists in this part because the 1
step smaller value of k
is k-1
. x
will remain same. Now it is
necessary to multiply it to x
to be equal to exp(x,k)
. Therefore, the
full expression becomes exp(x,k) = x times exp(x,k-1)
. Now together the
function is looks like:
1exp(x,k) =
2 1, when `k=0`
3 x times exp(x,k-1), otherwise
Obviously, the code for the above function is:
1int exp(int x, int k){
2 if( k == 0 )
3 return 1;
4 else
5 return x * exp( x, k-1 );
6}
Proof of correctness
Let us see whether the above function, exp(x,k)
is really x^k
. We
can prove it by using induction on k
.
Case 1. k=0
.
exp(x,0) = 1 | …(1) from the function |
x^0=1 | …(2) naturally |
herefore exp(x,0) = x^0 | from (1) and (2) |
Case 2. k eq 0
.
We want to prove that exp(x,k)=x^k
. So, naturally exp(x,k-1)
supposed to be x^{k-1}
. We will take this as the induction hypothesis.
exp(x,k-1) = x^{k-1} | …(1) by induction hypothesis |
so, x times x^{k-1} = x^{k-1+1} | we know from arithmatic |
so, x times x^{k-1} = x^k | k-1+1=k |
so, x times exp(x,k-1) = x^k | from (1) |
herefore exp(x,k) = x^k | from the function |
Factorial is another arithmetic function that is informally,
x! = x times (x-1) times ... times 1
. We can define it
recursively. First, it has the only parameter, x
. We know that x
can
be at least 0
and factorial(0)=1
. This is our base
part. Now in the recursion part it must contain
factorial(x-1)
. Finally, we can multiply it with x
to
make it equal to factorial(x)
. See the proof later for a
better understanding.
Now our function looks like:
1factorial(x)=
2 1 , when `x=0`
3 x times factorial(x-1), otherwise
Obviously, the code for the above function is:
1int factorial(int x){
2 if( x == 0 )
3 return 1;
4 else
5 return x * factorial( x - 1 );
6}
Proof of correctness
Let us see whether the above function, factorial(x)
is
really x!
. We can prove it by using induction on x
.
Case 1. x=0
.
factorial(0) = 1
by definition, 0! = 1
Case 2. x eq 0
.
We want to prove that factorial(x)=x!
. So, naturally
factorial(x-1)
supposed to be (x-1)!
. We will take this
as the induction hypothesis.
factorial(x-1) = (x-1)! | …(1) by induction hypothesis |
(x-1)! = (x-1) times (x-2) times ... times 1 | expanded form |
so, x times (x-1)! = x times (x-1) times (x-2) times ldots imes 1 | multiplying both side by x |
so, x times factorial(x-1) = x! | from (1) |
herefore factorial(x) = x! | from the function |
Now our function looks like:
1{hbox{em fibonacci}}(x)=begin{dcases*}
2 0 & when `x=0`
3 1 & when `x=1`
4 {hbox{em fibonacci}}(x-1) + {hbox{em fibonacci}}(x-2) & otherwise
5 end{dcases*}
Obviously, the code for the above function is:
1int fibonacci(int x){
2 if( x == 0 )
3 return 0;
4 else if( x == 1 )
5 return 1;
6 else
7 return fibonacci( x - 1 ) +
8 fibonacci( x - 2 );
9}
1{hbox{em add}}(x,y)=begin{dcases*}
2 x & when `y=0`
3 suc({hbox{em add}}(x,y-1)) & otherwise
4 end{dcases*}
Obviously, the code for the above function is:
1int suc(int x){
2 return x + 1;
3}
4
5int add(int x, int y){
6 if( y == 0 )
7 return x;
8 else
9 return suc( factorial( x - 1 ) );
10}
Write a recursive function to represent multiplication of two numbers by using only addition. Write a recursive function to represent integer division of two numbers by using only subtraction.
1sum_{i=1}^ni^4 = 1^4 + 2^4 + ldots + n^4
Can be rewritten as:
1{hbox{em sumOfQuad}}(n)=begin{dcases*}
2 1 & when `n=1`
3 {hbox{em exp}}(n,4) + {hbox{em sumOfQuad}}(n-1) & otherwise
4 end{dcases*}
In C:
1int sumOfQuad(int n){
2 if( n == 0 )
3 return 0;
4 else
5 return exp( n , 4 ) +
6 sumOfQuad( n - 1 );
7}
A similar, in fact, more generalized series is:
1sum_{i=1}^ni^k = 1^k + 2^k + ldots + n^k
It can be rewritten as:
1{hbox{em sumOfPow}}(n,k)=begin{dcases*}
2 1 & when `n=1`\n {hbox{em exp}}(n,k) + {hbox{em sumOfPow}}(n-1,k) & otherwise
3 end{dcases*}
It is converted into the program:
1int sumOfPow(int n, int k){
2 if( n == 0 )
3 return 0;
4 else
5 return exp( n, k ) +
6 sumOfPow( n - 1, k );
7}
A general product series can be rewritten as:
1prod_{i=1}^ni^k = 1^k times 2^k times ldots times n^k
See how we can get a product series from the previous series by only
changing the base case result and by replacing +
by times
in the
recursion part. Obviously, we should change the name of the function.
1{hbox{em prodOfPow}}(n,k)=begin{dcases*}
2 1 & when `n=1`
3 {hbox{em exp}}(n,k) times {hbox{em prodOfPow}}(n-1,k) & otherwise
4 end{dcases*}
Here is the code:
1int prodOfPow(int n, int k){
2 if( n == 0 )
3 return 1;
4 else
5 return exp( n, k ) *
6 prodOfPow( n - 1, k );
7}
In this example, we will calculate the natural square root of a number
n
. A natural square root is a natural number that is an integer and also
positive. We will examine a very easy function to do that. In this
function, 0
will first be tested if it is the square root of n
. If
the square root of n
is not a natural number, the smallest larger
value (sqrt{n}+1
) will be accepted as an approximation. For each test
fails, the next natural number will be tested similarly.
The logic behind the condition square(k) >= n
is that
sqrt{n} = k
if and only if k^2 = n
and sqrt n+1 = k+1
and then
(k+1)^2 > n
. Since the value of k
is increasing from
0
one by one, either sqrt n
of sqrt n+1
will be
accepted as the natural square root of n
.
1int square(int x){
2 return x*x;
3}
4int squareRootNatTest(int n, int k){
5 if( square(k) >= n )
6 return k;
7 else
8 return squareRootNatTest(n, k+1);
9}
10int squareRootNat(int n){
11 return squareRootNatTest(n, 0);
12}
Can you explain how the code below determines a number as a prime?
1int doesDivides(int x, int y){
2 return (x % y) == 0;
3}
4int primeTest(int i, int n){
5 if( i == n )
6 return 1;
7 else if( doesDivides(n, i) )
8 return 0;
9 else
10 return primeTest(i+1, n);
11}
12int isPrime(int n){
13 return primeTest(2, n);
14}
Problem: Suppose we have a two-dimensional grid of N
columns and M
rows. We name a cell of it in terms of its vertical and
horizontal index (x
,y
). We have a robot that can move either to one
cell left or one cell below. It cannot cross the border of the grid
indeed. Let’s place the robot at any cell in the grid and our current
challenge is to know the number of ways it can reach to the bottom-left
most corner, cell (0
,0
).
Solution: Lets imagine a grid of N=9
columns and
M=5
rows where the robot is placed at the cell (6
,3
).
The goal of its move is to reach the cell (0
,0
). It can
move only downward or left.
If the robot is placed in the cell (0
,0
), it needs 0
move to reach
the goal and hence trivially there is only one way to reach the goal.
From all the cells in the left-most column ((0
,1
), (0
,2
),
ldots
), the robot can move only downward. So, from each of these
positions (where x
is 0
), the robot has only one way to reach the
goal. Similarly, from all the cells at bottom-most row (where y
is
0
), it has only one way to reach the goal. From any other cell, the
path to reach the goal depends on its left and below adjacent cells. So,
the number of possible ways to reach the goal can be determined by
adding that of those two cells. So, our function is as follows:
1{hbox{em ways}}(x,y)=begin{dcases*}
2 1 & when `x=0` or `y=0`
3 ways(x-1,y)+ways(x,y-1) & otherwise
4 end{dcases*}
Now we can write our function in C very easily:
Operator | Name |
---|---|
! | Not |
|| | Or (Logical) |
&& | And (Logical) |
1int ways(int x, int y){
2 if( x == 0 || y == 0 )
3 return 1;
4 else
5 return ways( x-1, y ) + ways( x, y-1 );
6}