## Build-Up Your Problem Solving Skill : Specially Using By C/C++/Data Structure Puzzles/New Technique Algorithm Design/ Understanding New Technology ravi on Google Interview Latest ravi on Google Interview Latest asadullahansari on solve this puzzle? asadullahansari on solve this puzzle? asadullahansari on solve this puzzle?

• 1,343 hits

# Archive for the ‘C/C++ Developer’ Category

## write a program for bit count in a 32-bit integer number?

Posted by asadullahansari on August 21, 2008

Program should be efficient. Dont count every bit by loop…Cheers!!!!

Posted in C/C++ Queries & Ans | 1 Comment »

## Can You tell me All cases where Initialization list is mandatory in C++?

Posted by asadullahansari on August 20, 2008

Can you please tell me all possible cases where Constructor Initialization list is mandatory?

Posted in C/C++ Queries & Ans | 2 Comments »

## C/C++ Developer: Detail About Recursion and its Type

Posted by asadullahansari on July 4, 2008

Introduction

Here I am going to give a detail about Recursion in C++. Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.

Many complex problem can be solved by recursion in a simple code. But it’s too much costly than iterative. because in every recursion call one stack frame will formed.You all already know that about it’s cost. but if problem is very complex than no way to solve except recursion.

Background

First recursion came into mathematics and then came into Computer science. Idea of it’s use that first broke your problem into subproblems and solve it by using recursion.

The code

In C++, Recursion can be divided into two types:
(a)Run- Time Recursion: Normal as in C
(b)Compile- Time Recursion: By using Template

Each of these can be also divided into following types:

1. Linear Recursion
2. Binary Recursion
3. Tail Recursion
4. Mutual Recursion
5. Nested Recursion

1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called ‘Winding’ and when it returns to caller that is called ‘Un-Winding’. Termination condition also known as Base condition.

Example: Factorial calculation by linear recursion

Run-Time Version

Code:
```
int Fact(long n)
{
if(0>n)
return -1;
if(0 == n)
return 1;
else
{
return ( n* Fact(n-1));
}
}```

Winding Process:

Function called Function return

Fact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)
Terminating Point
Fact(0) 1

Unwinding Process

Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1

Compile-Time Version

Code:
```
// template for Base Condition
template <>
struct Fact<0>
{
enum
{
factVal = 1
};
};

template
struct Fact
{
// Recursion call by linear method
enum
{
value = n * Fact::factVal
};
};```

To test it how it’s working at compile time, just call
cout <<>::factVal ;
And compile it then compiler error will come, because no template for -1.

2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it’s using in data structure like operations for tree as traversal, finding height, merging, etc.

Example: Fibonacci number

Run Time Version Code

Code:
```
int FibNum(int n)
{
// Base conditions
if (n < 1)
return -1;
if (1 == n || 2 == n)
return 1;    // Recursive call by Binary Method
return FibNum(n - 1) + FibNum(n - 2);
// At a time two recursive function called so Binary
}
//   binary }```

Compile Time Version Code

Code:
```
// Base Conditions
template<>
struct FibNum<2>
{
enum { val = 1 };
};
template <>
struct FibNum<1>
{
enum { val = 1 };
};

// Recursive call by Binary Method
template
struct FibNum
{
enum { val= FibNum::val + FibNum::val };
};```

3. Tail Recursion: In this method, recursive function is called at the last. So it’s more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.

Example: Fibonacci number

Run Time Version Code

Code:
```
int FibNum(int n, int x, int y)
{
if (1 == n)    // Base Condition
{
return y;
}
else        // Recursive call by Tail method
{
return FibNum(n-1, y, x+y);
}
}```

Compile Time Version Code

Code:
```
template
struct FibNum
{
// Recursive call By tail method
enum
{
val = FibNum::val
};
};

// Base Condition or Termination
template
struct FibNum<1,>
{
enum
{
val = y
};
};```

4. Mutual Recursion: Functions calling each other. Let’s say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it’s doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.

Example: To find Even Or Odd number

Run Time Version Code

Code:
```
bool IsOddNumber(int n)
{
// Base or Termination Condition
if (0 == n)
return 0;
else
// Recursive call by Mutual Method
return IsEvenNumber(n - 1);
}
bool IsEvenNumber(int n)
{
// Base or Termination Condition
if (0 == n)
return 1;
else
// Recursive call by Mutual Method
return IsOddNumber(n - 1);
}```

Compile Time Version Code

Code:
```
// Base Or Termination Conditions
template <>
struct IsOddNumber<0>
{
enum
{
val = 0
};
};
template <>
struct IsEvenNumber<0>
{
enum
{
val = 1
};
};

// Recursive calls by Mutual Method

template
struct IsOddNumber
{
enum
{
val = n == 0 ? 0 : IsEvenNumber::val
};
};

template
struct IsEvenNumber
{
enum
{
val = n == 0 ? 1 : IsOddNumber::val
};
};```

5.Nested Recursion: It’s very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.

Example: Ackermann function

Run Time Version Code

Code:
```
int Ackermann(int x, int y)
{
// Base or Termination Condition
if (0 == x)
{
return y + 1;
}
// Error Handling condition
if (x <> 0 && 0 == y)
{
return Ackermann(x-1, 1);
}
// Recursive call by Nested method
else
{
return Ackermann(x-1, Ackermann(x, y-1));
}
}```

Compile Time Version Code

Code:
```
// Base Or Termination condition
template
struct Ackermann<0,>
{
enum { val = y + 1 };
};

// Recursive Call by Linear Method
template
struct Ackermann
{
enum
{
val = Ackermann::val
};
};
// Recursive Call by Nested Method
template
struct Ackermann
{
Enum
{
val = Ackermann ::val>::val
};
};```

References

“Teaching recursion using recursively generated geometric design”
by Aaron Gordon

## Restriction on creation of object into heap, stack, static memory

Posted by asadullahansari on July 4, 2008

This is just for a kind of information.

Here I am going to explain how to make a class so that user can create object
of it on free List( heap memory) or Stack.

Example 1: Object should be created Only On Heap memory.Idea is that make
constructor as private so that no one create on stack. But one drawback is
that constructor can be overloaded so better make destructor as private
member of class because Destructor can’nt be overloaded. It’s very safe
to make destructor as private member of class for this purpose.

Code: Cpp
```

class HeapOnly
{
public:
void DestroyMe() //This function will call destructor
{
delete this;   // Current object will be deleted means destructor
}
private:
~HeapOnly();     // destructor only can be call by member function
};
```

Now you can test above class.

Code: Cpp
```

int main()
{
HeapOnly
HeapOnly * ptr = new HeapOnly;  // Object created on heap
ptr->DestroyMe()                // Object deallocated
}
```

Example 2: Object should be created Only On stack memory or static memory. Idea
is that just overload the new and delete operator and make it private member
and dummy implemetation.

Code: Cpp
```

class autoOnly
{
public:
autoOnly()
{
;
}
~autoOnly()
{
;
}
private:
void* operator new(size_t)
{
// Dummy Implementation
}
void* operator new[](size_t)
{
// Dummy Implementation
}
void operator delete(void*)
{
// Dummy Implementation
}
void operator delete[](void*)
{
//Dummy Implementation
}
};
```

Now you can test it .

Code: Cpp
```

int main()
{
autoOnly *ptr= new autoOnly; // Error " cannt Access private member
autoOnly obj;  // Created on stack
static autoOnly obj1;  //Created on static memory
return 0;
}
```

## Hello world!

Posted by asadullahansari on July 4, 2008

High Technician… Here i will post a lot of C/C++ Articles made by mine only.All articles are tested in Unix/Solaris operating system using gcc/g++ compiler.You can ask any questions/doubts any time.

Posted in C/C++ Developer | 2 Comments »