15. Recursion - 19 Questions

# 15. Recursion

19 Questions
Created by Y. Daniel Liang
Free
##### Recursion is a way of programming or coding a problem, in which a function calls itself one or more times in its body. Usually, it is returning the return value of this function call. If a function definition fulfils the condition of recursion, we call this function a recursive function. Termination condition: A recursive function has to terminate to be used in a program. A recursive function terminates, if with every recursive call the solution of the problem is downsized and moves towards a base case. A base case is a case, where the problem can be solved without further recursion. A recursion can lead to an infinite loop, if the base case is not met in the calls.
1. Which of the following statements are true?

Every recursive function must have a base case or a stopping condition.
Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.
Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.
All of the above

2. Fill in the code to complete the following function for computing factorial.

```def factorial(n):     if n == 0: # Base case         return 1     else:         return _____________________ # Recursive call```

n * (n - 1)
n
n * factorial(n - 1)
none of these

3. What are the base cases in the following recursive function?

```  def xfunction(n):       if n > 0:           print(n % 10)           xfunction(n // 10)```

n > 0
n <= 0
n < 0
no base cases

4. Analyze the following recursive function.

```  def factorial(n):       return n * factorial(n - 1)```

Invoking factorial(1) returns 1.
Invoking factorial(2) returns 2.
Invoking factorial(3) returns 6.
The function runs infinitely and causes a StackOverflowError.

5. Which of the following statements are true?

The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
The Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
The Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series.
The Fibonacci series begins with 2 and 3, and each subsequent number is the sum of the preceding two numbers in the series.

6. Fill in the code to complete the following function for computing a Fibonacci number.

```def fib(index):     if index == 0: # Base case         return 0     elif index == 1: # Base case         return 1     else: # Reduction and recursive calls         return _________________________```

fib(index - 1)
fib(index - 2)
fib(index - 1) + fib(index - 2)
fib(index - 1) - fib(index - 2)

7. In the following function, what is the base case?

```def xfunction(n):     if n == 1:         return 1     else         return n + xfunction(n - 1)```

n is 1.
n is greater than 1.
n is less than 1.
no base case.

8. What is the return value for xfunction(4) after calling the following function?

```def xfunction(n):     if n == 1:         return 1;     else:         return n + xfunction(n - 1)```

12
11
10
9

9. Fill in the code to complete the following function for checking whether a string is a palindrome.

```def isPalindrome(s):     if len(s) <= 1: # Base case         return True     elif _____________________________         return False     else:         return isPalindrome(s.substring(1, len(s) - 1))```

s[0] != s[-1]: # Base case
s[0] != s[len(s)]: # Base case
s[1] != s[len(s) - 1]: # Base case
s[1] != s[len(s)]: # Base case

10. Analyze the following code:

```def xfunction(x, length):     print(x[length - 1], end = " ")     xfunction(x, length - 1) x = [1, 2, 3, 4, 5] xfunction(x, 5)```

The program displays 1 2 3 4 6.
The program displays 1 2 3 4 5 and then raises an index out of range exception.
The program displays 5 4 3 2 1.
The program displays 5 4 3 2 1 and then raises an index out of range exception.

11. Fill in the code to complete the following function for checking whether a string is a palindrome.

```def isPalindrome(s):     return isPalindromeHelper(s, 0, len(s) - 1) def isPalindromeHelper(s, low, high):     if high <= low: # Base case       return True     elif s[low] != s[high]: # Base case       return False     else:       return ____________________________```

isPalindromeHelper(s, low, high)
isPalindromeHelper(s, low + 1, high)
isPalindromeHelper(s, low, high - 1)
isPalindromeHelper(s, low + 1, high - 1)

12. Fill in the code to complete the following function for sorting a list.

```def sort(lst):     _________________________ # Sort the entire list def sortHelper(lst, low, high):     if low < high:         # Find the smallest number and its index in lst[low .. high]         indexOfMin = low         min = lst[low]         for i in range(low + 1, high + 1):             if lst[i] < min:                 min = lst[i]                 indexOfMin = i         # Swap the smallest in list(low .. high) with list(low)         lst[indexOfMin] = lst[low]         lst[low] = min         # Sort the remaining list(low+1 .. high)         sortHelper(lst, low + 1, high)```

sortHelper(lst)
sortHelper(lst, len(lst) - 1)
sortHelper(lst, 0, len(lst) - 1)
sortHelper(lst, 0, len(lst) - 2)

13. What will displayed by the following code?

```def main():     times = count("abcabc", 'a')     print(ch + " appears " + str(times) + (" times " if times > 1 else " time ") + "in " + s)      def count(s, a):     return countHelper(s, a, len(s) - 1) def countHelper(s, a, high):     result = 0;     if high > 0:         result = countHelper(s, a, high - 1) + (1 if s[high] == a else 0)     return result; main()```

a appears 1 times in abcdabc
a appears 2 times in abcdabc
a appears 1 time in abcdabc
a appears 2 time in abcdabc

14. In Tower of Hanoi how many times is the recursive moveDisks function invoked for 3 disks?

3
7
10
14

15. In Tower of Hanoi how many times is the recursive moveDisks function invoked for 4 disks?

5
10
15
20

16. In the context of Tower of Hanoi analyze the following two programs:

```A: def xfunction(length):     if length > 1:         print(length - 1, end = " ")         xfunction(length - 1) xfunction(5) B: def xfunction(length):     while length > 1:         print(length - 1, end = " ")         xfunction(length - 1) xfunction(5)```

The two programs produce the same output 1 2 3 4 5.
The two programs produce the same output 4 3 2 1.
The two programs produce the same output 1 2 3 4.
Program A produces the output 4 3 2 1 and Program B runs infinitely.

17. Which of the following statements are true?

Recursive functions usually take more memory space than non-recursive functions.
A recursive function can always be replaced by a non-recursive function.
In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.
all of the above

18. Analyze the following functions;

```def f1(n):     if n == 0:         return 0     else:         return n + f1(n - 1) def f2(n, result):     if n == 0:         return result     else:         return f2(n - 1, n + result) print(f1(3)) print(f2(3, 0))```

f1 is tail recursion, but f2 is not
f2 is tail recursion, but f1 is not
f1 and f2 are both tail recursive
Neither f1 nor f2 is tail recursive

```def f2(n, result):     if n == 0:         return 0     else:         return f2(n - 1, n + result) print(f2(2, 0))```