SOME SIMPLE PROGRAMS USING RECURSION

Develop recursive programs for the following questions:

Question # 1

Display the following series using recursion:

1, 2, 3, 4, 5, 6, 7, 8……20

/***********************************************************************************/

#include<stdio.h>

#include<conio.h>

void print(int);

int main()

{

                print(20);

                getch();

                return 0;

}

void print(int n)

{

                if(n==0)

                                return;

                print(n-1);

                printf("%d\t",n);

}

/***********************************************************************************/

Question # 2

Display the following series using recursion:

20 , 19 , 18 , 17 , 16 …. 2 , 1

/***********************************************************************************/

#include<stdio.h>

#include<conio.h>

void print(int);

int main()

{

                print(20);

                getch();

                return 0;

}

void print(int n)

{

                if(n==0)

                                return;

                printf("%d\t",n);

                print(n-1);

}

/***********************************************************************************/

Question # 3

Calculate the factorial of a given number using recursion.

/***********************************************************************************/

#include<stdio.h>

#include<conio.h>

long factorial(int);

int main()

{

                int num;

                clrscr();

                printf("Enter the number : ");

                scanf("%d",&num);

                printf("%ld",factorial(num));

                getch();

                return 0;

}

long factorial(int n)

{

                long fact;

                if(n==0)

                                return 1;

                fact=factorial(n-1)*n;

                return fact;

}

/***********************************************************************************/

STATIC SCOPING AND DYNAMIC SCOPING

Languages such as Algol, Ada, C, and Pascal are statically scoped. A block defines a new scope. Variables can be declared in that scope, and aren't visible from the outside. However, variables outside the scope -- in enclosing scopes -- are visible unless they are overridden. In Algol and Pascal (but not C or Ada) these scope rules also apply to the names of functions and procedures.

In lexical scoping (or lexical scope; also called static scoping or static scope), if a variable name's scope is a certain function (that is, a particular variable is declared in that function), then its scope is the program text of the function definition: within that text, the variable name exists, and is bound to the variable's value, but outside that text, the variable name does not exist.

By contrast, in dynamic scoping (or dynamic scope), if a variable name's scope is a certain function, then its scope is the time-period during which the function is executing: while the function is running, the variable name exists, and is bound to its variable, but after the function returns, the variable name does not exist.

Consider the following example:

If function f invokes a separately defined function g, then under lexical scoping, function g does not have access to f's local variables (since the text of g is not inside the text of f), while under dynamic scoping, function g does have access to f's local variables (since the invocation of g is inside the invocation of f).

STATIC SCOPING

With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text and is made independent of the run-time call stack by the language implementation. Because this matching only requires analysis of the static program text, this type of scoping is also called static scoping.

Example of static scoping:

const int var = 5;

int g()

{

   int a = var + 5;

   return a;

}

int f()

{

   int var = 2;

   return g();

}

int main()

{

   g(); // returns 10

   f(); // returns 10

   return 0;

}

DYNAMIC SCOPING

With dynamic scope, each identifier has a global stack of bindings. Introducing a local variable with name x pushes a binding onto the global x stack (which may have been empty), which is popped off when the control flow leaves the scope. Evaluating x in any context always yields the top binding. In other words, a global identifier refers to the identifier associated with the most recent environment. Note that this cannot be done at compile-time because the binding stack only exists at run-time, which is why this type of scoping is called dynamic scoping.

Example of Dynamic scoping:

const int var = 5;

int g()

{

   int a = var + 5;

   return a;

}

int f()

{

   int var = 2;

   return g();

}

int main()

{

   g(); // returns 10

   f(); // returns 7

   return 0;

}

PROGRAM WHICH ACCEPTS AN EXPRESSION AND EVALUATES IT

Question:

Write a program that accepts an expression and evaluates it.

Hint:

For the purpose of simplicity, the following assumptions can be taken:

1. Symbols representing operations are one character long.
2. All operations are binary operations.
3.  Input is in infix format.

Solution:

/**********************************************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int Remove(float*,char*,int,int);

int check(char ,float*,char*,int );

void print(float*,char*,int);

int main()

{

                char str[200],*ops;

                int number=0,c_number,i,j;

                float*num;

                clrscr();

                printf("ENTER THE EXPRESSION : \n");

                printf("THE EXPRESSION SHOULD BE IN INFIX FORMAT AND SHOULD NOT INCLUDE SPACES...\n");

                scanf("%s",str);

                i=0;

                while(str[i])

                {

                                if((int)str[i]<48||(int)str[i]>57)

                                                number++;

                                i++;

                }

                number++;

                //number stores the total number of operands

                num=(float*)malloc(sizeof(float)*(number));

                ops=(char*)malloc(sizeof(char)*(number-1));

                for(i=0;i<number;i++)

                                num[i]=0;

                i=j=0;

                while(str[i])

                {

                                if((int)str[i]<48||(int)str[i]>57)

                                                ops[j++]=str[i];

                                i++;

                }

                i=j=0;

                while(str[i])

                {

                                while(((int)str[i]>=48&&(int)str[i]<=57))

                                                num[j]=num[j]*10+(int)str[i++]-48;

                                i++;j++;

                }

                c_number=number;

                for(i=0;i<c_number-1;i++)

                {

                                number=check('/',num,ops,number);

                                number=check('*',num,ops,number);

                                number=check('-',num,ops,number);

                                number=check('+',num,ops,number);

                }

                printf("\n\nFinal Answer = %g\n",num[0]);

                getch();

                return 1;

}

int check(char op,float*num,char*ops,int number)

{

                int j;

                while(1)

                {

                                j=0;

                                while(ops[j]!=op&&j<number)

                                {

                                                j++;

                                                if(j>number-1)

                                                                break;

                                }

                                if(j>number-1)

                                                return number;

                                if(j<number-1)

                                {

                                                if(op=='/')

                                                                num[j]=num[j]/num[j+1];

                                                else if(op=='*')

                                                                num[j]=num[j]*num[j+1];

                                                else if(op=='+')

                                                                num[j]=num[j]+num[j+1];

                                                else

                                                                num[j]=num[j]-num[j+1];

                                                number=Remove(num,ops,j,number);

                                                continue;

                                }

                                break;

                }

                return number;

}

void print(float*num,char*ops,int number)

{

                int i;

                for(i=0;i<number-1;i++)

                                printf("%g %c ",num[i],ops[i]);

                printf("%g\n",num[i]);

}

int Remove(float *num,char *ops,int j,int number)

{

                int i;

                for(i=j+1;i<number-1;i++)

                {

                                num[i]=num[i+1];

                                ops[i-1]=ops[i];

                }

                number--;

                print(num,ops,number);

                return number;

}

/**********************************************************************************/