QUIZ 9

Give an example of a problem that can be implemented more efficiently with an iterative rather than a recursive algorithm.
______________________________________________________
What sequence does the following function produce?
```
long Function(int n)
{
	if(n==0||n==1)
		return(1);
	else
		return 2*Func(n-2)+Func(n-1);
}
```
1. 1, 1, 2, 3, 5, 8, 13
2. 2n, n=0, 1, 2....
3. 1,1, 3,5, 11, 21...
4. 1, 1, 5,13, 41, 121...

What is an equivalent non-recursive version of the following function?

int Func(int n)
{
	if(n>0)
		return 1+Func(n-1)
	else
		return 0;
}

 int Func(int n)
{
	int temp=0;
	for(int i=0;i<n;i++)
		temp+=i;
	return temp;
}

int Func(int n)
{
	int temp=0;
	for(int i=0;i<n;i++);
		temp+=n;
	return temp;
}

```
int Func(int n)
{
	return n;
}
```

int Func(int n)
{
	int temp=0;
	for(int i=1; i<=n;i++)
		temp+=n-i;
	return temp;
}

Trace the function calls assuming the VALUE is initially 0. Give the corresponding output.
```
void Func(int n, int bound, lon &val)
{
	if (n<=bound)
		{
			if(n%2==1)	//n is odd
				val+=n;
			else
				val -=n;
			Func(n+1,bound, val);
		}
}
```
1. Func(1, 6, VALUE) VALUE is _____
  1. 21
  2. -3
  3. 3
  4. -6
2. Func(2, 5, VALUE) VALUE is_____
  1. -3
  2. -5
  3. 4
  4. 2
Trace the following function
```
void Func(char s[], int n, int m)
{
	char temp;
	
	if(m<=n)
		return;
	else
	{
		temp=s[n];
		s[n]=s[m];
		s[m]=temp;
		Func[s, n+1, m-1];
	}
}
```
1. Start with rhe string str="kcul doog". After the call, Func(str, 0, strlen(str)) str=___________________
2. Start with rhe string str="level". After the call, Func(str, 0, strlen(str)) str=___________________
Trace the recursive code that uses the Swap function to exchange the designated arrays.
```
int arrvalue(int a[], int n)
{
	if(n>0)
		Swap(a[n], a[n-1]);
	arrvalue(a, n-1);
}
```
1. For list A=(1, 2, 3, 4) call arrvalue(A, 3). The modified list is A_____
2. For list A=(4, 7, 2, 1, 5) call arrvalue(A,4). The modified list is A_____
The following recursive code identifies string patterns. Trace the code and identify the pattern.
```
int pat(char str[], int i)
{
	int m=strlen(str)/2;
	if(i>=m)
		return 1;
	else
		if(A[i]!=A[m+i])
			return 0;
	else
		return pat(A, i+1);
}
```
1. Which of the following functions is recognised by the function pat
  1. 123321
  2. 123123
  3. 1234321
  4. none of these
3. Which of the following functions is recognised by the function pat
  1. powwow
  2. sees
  3. poppep
  4. none of these
A function that contains a void parameter list cannot be a recursive function
1. true
2. false
A void function cannot be a recursive function.
1. true
2. false
There are situations when a recursive solution to a problem is more appropriate than an iterative one.
1. true
2. false.
Identify a string that is valid for the following BNF definition.
```
<Str>::=<Str>A|<NextStr>B
<NextStr>::=C|<NextStr>C
```
1. AABBCC
2. CCBAAA
3. CCABC
4. ABCABC