Objective: To Practice recursion/ think recursively.
Description:
A Recursive task is a task that is defined in the terms of itself. Recursive function calls itself. With each invocation, the problem is reduced to a smaller task (reducing case) until the task arrives at some terminal case. A recursive function has two parts:
1. Terminal/base case. a stopping conditions.
2. Reducing case/recursive step an expression of the computation or definition in terms of itself.
EXAMPLE:
if
(terminal_condition)
terminal_case
else
reducing_caseThe
factorial function:
n! = n * (n-1) * (n -2) * … * 2 * 1. The
same function can be defined recursively as follows:
1. 0! = 1 – 1. terminal case
2. n! = n * (n - 1)! - the reducing case
EXAMPLE:
dnint fact
(int n)
if
(n==0) // base case
return 1;
else // reducing case
return n*fact(n-1)
Programming
languages typically have local variables. That is created upon entry to
function and Destroyed when function returns. Each invocation of a function has
its own instantiation of local variables. Recursive calls to a function require
several instantiations to exist simultaneously. Functions return only after all
functions it calls have returned last-in-first-out (LIFO) behavior. A LIFO
structure called a stack is used to hold each instantiation. The portion of the
stack used for an invocation of a function is called the function’s stack frame
or activation record.
Example:
Let us
consider the above factorial example to understand activation records.
Recursion elimination using stacks:
Recursion
is implemented in via the system stack.
Each recursive call to a method requires that the following information
be pushed onto the system stack:
·
Formal
Parameters
·
Local
Variables
·
Return
Address
This
information, collectively, is referred to as a stack frame. The stack frame for each method call will be
different. For example, the stack frame
for a parameter less/no local variable method will contain just a return
address. All this is transparent to us
as users because this happens magically due to the compiler. When we make a
call to a recursive method, the compiler has taken care of the entire above
required stack maintenance. To aid in
our understanding of the process that takes place during the execution of a
typical recursive routine, it is instructional to simulate it by managing this
stack frame ourselves (not let C++/Java do it) with our own Stack. The
following strategy can be used to the remove the recursion from a recursive
routine, although not elegantly. There
might be a far more pleasing method for a particular routine, but this technique
is very instructional. It allows you
simulate the system stack by declaring your own stack structure and manage the
recursion. It is accomplished as
follows:
1. Each time a recursive call is made in the
algorithm, push the necessary information onto your stack.
2. When you complete processing at this deeper
level, pop the simulated stack frame and continue processing in the higher
level at the point dictated by the return address popped from the stack.
3. Use an iterative control structure that loops
until there are no return addresses left to pop from the stack.
The use
of a switch statement might help with the return address location.
WITH THE HELP OF FOLLOWING EXAMPLES WE WILL TRY TO UNDERSTAND THIS TOPIC.
1. Write a recursive function to find the elements
multiple of 3 and at index multiple of 2 from given array
2. Write a recursive function power (int n, int x)
to find .
3. Write a function to Print alternate nodes of a
linked list using recursion.
|
CODE(1): #include <iostream>
using namespace std;
void print_array(int a[], int j)
{
// using the static variable
static int i;
// base case
if (i == j)
{
i = 0;
cout << endl;
return;
}
|
}
// print the ith element
if (a[i] % 3 == 0
|| i % 2 == 0)
cout << a[i] << " ";
i++;
// recursive call
print_array(a, j);
}
int main()
{
int arr[] = {
11,36,69,43,15,34,67,72,68 };
int n = sizeof(arr) / sizeof(arr[0]);
print_array(arr, n);
} OUTPUT:
|
CODE(2):
#include <iostream>
using namespace std;
int power(int n, int x)
{
if (x == 0)
{
return 1;
}
else
{
return n * power(n, x - 1);
}
}
int main()
{
int a = 0;
int b = 0;
cout << "Enter
the base = ";
cin >> a;
cout << "\nEnter
the power = ";
cin >> b;
cout << "\nThe
" << a << " raise to power " << b << " = " << power(a, b);
}
|
Output:
CODE(3): #include <iostream> using namespace std; struct node { int data; node* next; }; class LinkedList { public: node* head; LinkedList() { head = NULL; } bool isEmpty() { if (head == NULL) { return true; } else return false; } void iAs(int data) { node* s = new node; (*s).data =
data; (*s).next =
NULL; if (head == NULL) { head =
s; } else {
(*s).next = head; head =
s; } } void iAAp(int pos, int data) { if (pos == 1) { iAs(data); } else { node* p = new node;
(*p).data = data;
(*p).next = NULL; node* temp =
head; for (int i = 1; i < pos - 1; i++) {
temp = (*temp).next; }
(*p).next = (*temp).next;
(*temp).next = p; } } void iAe(int data) { node* e = new node; (*e).data =
data; (*e).next =
NULL; if (head == NULL) { head =
e; } else { node* temp; temp =
head; while ((*temp).next
!= NULL) {
temp = (*temp).next; }
(*temp).next = e; } } void dAs() { node* temp = new node; temp =
head; head =
(*head).next; delete temp; } void dAAp(int nodepos) { if (isEmpty()) { cout << "The list is Empty....!!!!!"; } if (nodepos == 1) { dAs(); } else { node* temp1, *
temp2; temp1 =
head; for (int i = 1; i < nodepos - 1; i++) {
temp1 = (*temp1).next; } temp2 =
(*temp1).next;
(*temp1).next = (*temp2).next; delete temp2; } } void dAe() { node* temp =
head; node* temp2 =
(*temp).next; while ((*temp2).next
!= NULL) { temp =
(*temp).next; temp2 =
(*temp2).next; } delete temp2;
(*temp).next = NULL; } void Traverse() { if (isEmpty()) { cout << "The list is Empty....!!!!!"; } else { node* n =
head; while (n != NULL) {
cout << (*n).data << " "; n =
(*n).next; } cout << endl; } } void print_alt(node*temp) { if (!isEmpty()) { cout << temp->data << " "; if (temp->next == NULL) delete temp; else {
print_alt(temp->next->next); } } else return; } LinkedList(const LinkedList&
a) { head = a.head; if (isEmpty()) { head = NULL; } else { node* temp =
head; node* n = new node;
(*n).data = (*temp).data; head =
n;
(*temp).next = (*head).next; node* temp2 =
head; while (temp != NULL) { node* b = new node;
(*temp2).next = b;
(*temp2).data = (*temp).data;
temp = (*temp).next;
temp2 = (*temp2).next; }
(*temp2).next = NULL; } } ~LinkedList() { if (isEmpty()) { head = NULL; } else { node* temp1, *
temp2; temp1 =
head; temp2 =
(*temp1).next; while (temp2 != NULL) { delete temp1;
temp1 = temp2;
temp2 = (*temp2).next; } head = NULL; } } }; int main() { LinkedList
MyList; for (int i = 1; i <=
5; i++) {
MyList.iAAp(i, i); }
MyList.Traverse(); cout << "The alternate nodes of list : "<<endl;
MyList.print_alt(MyList.head);
} OUTPUT:
|
|
No comments:
Post a Comment