Data Structures & Algorithms 1st Year Sheet #4
Cairo University
Faculty of Engineering
Computer Engineering Department
Data Structures and Algorithms
Sheet #4
Recursion
Part I: Exercises
1. Consider the following recursive algorithm:
a. Show the output and draw the sequence of recursive calls of the following:
i. func (10, 4)
ii. func (4, 4)
iii. func (4, 7)
Algorithm func (x, y)
//Input: 2 integers x and y
if x > y return -1
elseif x = y return 1
else return x * func (x + 1, y)
2. Consider the following recursive algorithm:
a. Show the output and draw the sequence of recursive calls of the following:
i. S(1)
ii. S(5)
b. What does the algorithm compute?
Algorithm S(n)
//Input: a positive integer n
if n = 1 return 1
else return S(n-1) + n*n*n
3. Consider the following recursive algorithm:
a. Show the output and draw the sequence of recursive calls of the following:
i. Riddle1([2, 3], 2)
ii. Riddle1([3, 5, 4, 1, 2], 5)
b. What does the algorithm compute?
Algorithm Riddle1(A, n)
//Input: An array A of real numbers of length n
if n = 1 return A[0]
temp←Riddle1(A, n-1)
if temp ≤ A[n − 1] return temp
else return A[n − 1]
4. Consider the following recursive algorithm:
a. Show the output and draw the sequence of recursive calls of the following:
i. Riddle2([2, 5, 3, 6], 0, 3)
ii. Riddle2([3, 5, 4, 1, 2], 0, 4)
b. What does the algorithm compute?
Algorithm Riddle2(A, first, last)
//Input: An array A of real numbers and 2 integers first and last
if first = last return A[first]
mid = (first+last)/2
temp1←Riddle2(A, first, mid)
temp2←Riddle2(A, mid + 1, last)
if temp1 ≤ temp2 return temp1
else return temp2
CMP 102 & CMP N102 1/2 Spring 2018
Data Structures & Algorithms 1st Year Sheet #4
5. Does it matter where you position your recursive call in your function?
Given two versions of recursive function that searches for a given value in a linked list; what
is the difference between the two functions? Which one is better and why?
Test the two functions if linked list L = [10]→[12] → [4]→[7]→[56]→[9]→# and val=12.
Node* RecSearch1(Node *L, int val) Node* RecSearch2(Node *L, int val)
{ {
if(L == NULL) return NULL; if(L == NULL) return NULL;
if(L->data == val) return L;
Node *P = RecSearch2(L->Next, val);
return RecSearch1(L->Next, val); if( P != NULL) return P;
} if(L->data == val) return L;
else return NULL;
}
Part II: Problems
1. Write a recursive a logarithm to get the sum of series 1+2+3+4+…+n.
2. Write a recursive algorithm to add the first n elements of the series:1+1/2+1/3+1/4+1/5+...+1/n
3. Write a recursive algorithm that calculates and returns the sum of array elements.
4. Write a recursive algorithm to count number of occurrences of a value in an array.
5. Write a recursive algorithm that calculates and returns the length of a linked list.
6. Write a recursive algorithm to compute the sum of even numbers in a linked list.
7. Write a recursive algorithm to print a linked list in a forward order. What are the modifications to print
it reversed?
8. Write a recursive algorithm to print numbers read from keyboard in a forward order. What are the
modifications to print them reversed? (Note: don’t store numbers in an array; just print)
9. Compare the recursive solution of print reverse of problem 7 and 8 with the stack solution.
10. Compare the recursive solution of print forward of problem 7 and 8 with the iterative solution.
11. Write a recursive algorithm that returns the index of the first occurrence of an element in array if
found and -1 if not found. What are the modifications to return the index of last occurrence?
12. Write a recursive algorithm to check whether a linked list is sorted in an increasing order.
13. Write a recursive algorithm that checks whether a string is a substring of another string.
14. Write a recursive algorithm that converts a string of numerals to an integer. For example, “43567” will
be converted to 43567. (Hint: 43567 = 4*10000+3*1000+5*100+6*10+7*1)
15. Write a recursive C++ function to get the length of a circular linked list (Hint: you should send the
head of the original list too in each call; 2 inputs)
16. Write a recursive algorithm that reverses a linked list (without using new nodes). (Hint: make each
next pointer points to previous. It’s simple if you think recursively)
17. Solve palindrome problem (stack problem 2, sheet 4) using recursion. (Hint: check the first
character with the last character)
18. Solve Josephus problem (problem 11, sheet 3) using recursion.
CMP 102 & CMP N102 2/2 Spring 2018
