FATIMA JINNAH WOMEN UNIVERSITY

Department : Software Engineering

Name : Muneeba Mehmood

Section : B

Reg no : 2020-BSE-54

Subject : DATA STRUCTURE

Semester : III

Lab 2

 QUESTION#1:
Write the output of the following program.

PROGRAM:

// DSLAB2.cpp : Defines the entry point for the console application.

#include<iostream>
using namespace std;
int mystery(int,int);
int main()
{
int x=3,y=2;
cout<<"Result = "<<mystery(x,y);
return 0;
}
int mystery(int a, int b)
{
if(b==1)
return a;
else
return a + mystery(a, b-1);

 QUESTION#2:
Let J and K be integers and suppose Q(J, K) is recursively defined by :
Q(J,K) = {
5, J < K
Q(J − K, K + 2) + J, J ≥ K
Trace and Find Q(5, 3).

PROGRAM:

// DSLAB2.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include<iostream>
using namespace std;
int Q(int,int);

int _tmain(int argc, _TCHAR* argv[])

int x=5,y=3;
cout<<"Result = "<<Q(x,y);
cout<<endl;
system("pause");
return 0;
}
int Q(int j, int k)
{
if(j<k)
return 5;
else
return (Q(j-k, k+1) +j);

}
  QUESTION#3:
Let ‘a’ and ‘b’ be integers and suppose Q(a, b) is recursively defined by :
Q(a, b) = {0, a < b
Q(a − b, b) + 1, b ≤ a
Find Q(14,3).

PROGRAM:

// DSLAB2.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include<iostream>
using namespace std;
int Q(int,int);

int _tmain(int argc, _TCHAR* argv[])

return 0;
}
int Q(int a, int b)
{
if(a<b)
return 0;
else
return (Q(a-b,b) +1);

}
  QUESTION#4:
Identify the problem with following recursive function.
void recurse( int count )
{
cout<< count <<"\n";
recurse ( count + 1 );
}
ANSWER:

It will not run because recursive case is present but to stop recursion, the base case
is not present.

 QUESTION#5:
Given the following function, write the output if the user enters ‘abcz’ as input.
void rev()
{
char c;
cin>>c;
if(c!='z'){
rev();
cout<<c;
}
}

 EXERCISE#1:
Write a function sum(int a[], int size) to (recursively) compute the sum of the
elements in an array.

Example Run :

int arr[]={1,2,3,4} ;

int result = sum(arr,4) ;

cout<<result<<endl ; //Should print 10

PROGRAM:
// labofds.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int sum(int a[],int s)
{
if(s==0)
return 0;
else
return (a[s-1]+sum(a,s-1));}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={1,2,3,4};

int temp=sum(a,4);
cout<<"the result is " <<temp<< endl;
system("pause");
return 0;
}

 EXERCISE#2:
Write a recursive function to print integers from a given number N to 0. When
called as print (10), the function should print : 10 9 8 7 6 5 4 3 2 1 0.

PROGRAM:
// ds2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int print(int a){
if(a==1)
return 0;
else
cout<<a;
return print(a-1);}
int _tmain(int argc, _TCHAR* argv[])
{
int a=10;
cout<<"the result is " <<endl;
cout<<print(a)<< endl;
system("pause");
return 0;
}

 EXERCISE#3:
Ackermann’s function is defined recursively on non-negative integers as follows.

A(m,n) = n+1 if m == 0

A(m,n) = A(m-1, 1) if m != 0, n == 0

A(m,n) = A(m-1, A(m, n-1)) if m != 0, n != 0

Implement it as a recursive function Ackermann(M,N) which takes two positive

PROGRAM:
// ds2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int Akr(int n,int m);
int _tmain(int argc, _TCHAR* argv[])
{
int x,y;
cout<<"the result is for argument b(0,0) is "<<Akr(2,0)<<endl;
system("pause");
return 0;}
int Akr(int n,int m){

if(m==0)
return (n+1);
if((m!=0)&&(n==0))
return Akr(n-1,1);

if((m!=0)&&(n!=0))
return Akr(m-1,Akr(m,n-1));

 EXERCISE#4:
Binomial coefficients can also be computed using the following recursive
definition .Write a C++ program to compute binomial coefficients using the
mentioned recursive definition.

PROGRAM:
// ds2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int b(int,int);
int _tmain(int argc, _TCHAR* argv[])
{

cout<<"the result is "<<b(10,6)<<endl;

system("pause");
return 0;}
int b(int n,int m){

if(m==0)
return 1;
if(n==m)
return 1;
else
return ((n+1,m)+(n-1,m-1));
}

#include "stdafx.h"
#include<iostream>
using namespace std;
int b(int,int);
int _tmain(int argc, _TCHAR* argv[])
{

cout<<"the result is "<<b(10,0)<<endl;

system("pause");
return 0;}
int b(int n,int m){

if(m==0)
return 1;
if(n==m)
return 1;
else
return ((n+1,m)+(n-1,m-1));
}