In the previous sections, We introduced you to Binary
Search and Merge Sort, both of which had one thing in common, can you guess
what?
Both of them called themselves!
Like in Binary Search we said,
1. Goto the Middle of the array
2. If middle term is more than the number we are
looking for, run Binary Search
(calling itself) on the left side of the array, else look on the right side of
the array and if its equal, then return true.
…….
This is what is known as Recursion!
A function or method which calls itself is a
recursive function/method.
We may define functions which return a certain power
of a number as a recursive function and also the factorial function as a
recursive function.
NOTE: For those who don’t know what is factorial and
Exponent: The factorial of any integer ‘n’ is defined as the product of n and
all the numbers which are less than n, uptil 1.
The factorial of any number n is denoted by n!. Eg. (5! = 5x4x3x2x1, 4!
= 4x3x2x1 etc.).
Any integer a, raised to the bth
power,(denoted by ab) means a multiplied by itself for b number of
times. i.e. a2 = a x a, 25= 2 x 2 x 2 x 2 x 2 etc.
NOTE: The Following codes are not complete programs,
they are just declarations of functions of Factorial and Power/Exponent.
int factorial(n){
if(n
== 1){
return
1;
}else{
return
n*factorial(n-1);
}
}
int power(a,b){
if(b==1){
return
a;
}else{
return
a*power(a,b-1);
}
You may write a complete program testing these two
recursive functions to check for yourself and to make yourself comfortable with
recursion.
Recursion is a very useful programming tool, which is
used quite often, but always remembers one thing that if there’s a function
which could be run as both recursive and iterative (with loops!), then the loop
implementation would always be faster than the recursive one, for reasons you
may search for on Google.
Now Then, Let’s move on to memory,
The notion of Memory is not quite related to the study
of algorithms and data structures, but since it was a bit trivial, we had
decided to put it in this section.
A Computer stores all the variables and arrays we
declare in our program, in form a table with indexes and therefore, whenever we
declare a variable it provides that variable some particular amount of Space in
the memory(in what we call RAM!) and that space is referred to by a pointer!
Pointers are one of the most error-prone things in
Programming, because they are so complicated, that even thinking about them in
a complicated way will confuse you, but if you think of it in the sense of the
actual word then everything will seem to be quite clear.
You may also think of a pointer as an address to some
particular space in memory as well. An address which you could manipulate.
When we declare an array as ‘int arr[n]’, here the
‘arr’ is actually a pointer which points to some particular point in memory
where a lot elements could be stored contiguously, one after another as a
string or container of elements.
In C, many times you need to declare variables as
pointer and manipulate them, this is known as Dynamic Memory Allocation and is
considered one of the most hectic tasks in Programming. In C++(which is a more
convenient language in a manner of speaking!), its not that hectic, All you got
to do if you want to have some memory provided to you is something like the
following:
#include <iostream>
using namespace std;
int main(){
int*
arr;
arr
= new int[10];
for(int
i = 0;i<10;i++){
cin>>arr[i];
}
cout<<”Here’s
the Numbers you entered:”<<endl;
for(int
j = 0;j<10;j++){
cout<<arr[j]<<’
‘;
}
cout<<endl;
delete[]
arr;
}
Here, ‘new’ is an operator/function which does one
simple thing, it allocates space for one array or one variable. Its as if it
asks the Computer for space to store a certain number of elements at any given
pointer i.e. At any given point in Memory which is indicated by a pointer.
‘delete’ is a function/operator which is used to return the space which was
allocated to that particular pointer so, Pointers aren’t exactly like addresses
but they are similar to addresses!
And at last coming to Structs,
Structs are a form of an artificial data type. You
may remember that we told you of some of the most basic data types, i.e. int,
char, float, double, long etc.
But suppose that you are to build a program and you
need to store an array of something intricate (for example, lets say we are to
store the details of some contacts in a phone).
Here’s how we would do so in code:
#include <iostream>
#include <string>
using namespace std;
typedef struct Contact{
string
name;
string
email;
long
number;
}Contact;
int main(){
int
n;
cout<<"Hello,
Welcome to your own phone book!"<<endl;
cout<<"How
many Phone Numbers would you like to have?"<<endl;
cin>>n;
Contact
arrayOfContacts[n];
for(int
i = 0;i<n;i++){
cout<<"Enter
Details of the "<<i+1<<"st Contact:"<<endl;
cout<<"Enter
her/his Name:";
cin>>arrayOfContacts[i].name;
cout<<endl<<"Enter
her/his Email:";
cin>>arrayOfContacts[i].email;
cout<<endl<<"Enter
her/his Phone Number:";
cin>>arrayOfContacts[i].number;
cout<<endl;
}
cout<<"Here's
your Phonebook:"<<endl;
for(int
j = 0;j<n;j++){
cout<<j+1<<".
"<<"Name: "<<arrayOfContacts[j].name<<"
Email: "<<arrayOfContacts[j].email<<" Number:
"<<arrayOfContacts[j].number<<endl;
}
}
Note here that all we do is declare another data type
by the name Contact, and then use it as we did with normal data types, the only
difference is that we use a ‘.’ to exploit some particular property/attribute
of that particular data type and to store number In it.
The General syntax of defining a Data Type in C/C++
is:
typedef struct ‘name of data type’{
‘attributes/properties
of data types preceded by the attributes’ data type’
}’name of data type’;
NOTE: In C++, There’s another notion of a Class,
which could also be declared similar to a struct definition but also allows us
to define certain functions and set variables as well as functions as
public/private/friend inside of the class based on what we want it to be. One
could read more about a class by searching of it on Google!
Comments
Post a Comment