15. Recursion - 19 Questions


15. Recursion

15. Recursion

19 Questions
Created by Y. Daniel Liang - http://www.cs.armstrong.edu/liang/index.html
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

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  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.

    View Answer | Discuss in forum
  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.

    View Answer | Discuss in forum
  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)

    View Answer | Discuss in forum
  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.

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  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.

    View Answer | Discuss in forum
  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)

    View Answer | Discuss in forum
  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)

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  14. In Tower of Hanoi how many times is the recursive moveDisks function invoked for 3 disks?



    3
    7
    10
    14

    View Answer | Discuss in forum
  15. In Tower of Hanoi how many times is the recursive moveDisks function invoked for 4 disks?



    5
    10
    15
    20

    View Answer | Discuss in forum
  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.

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  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

    View Answer | Discuss in forum
  19. Show the output of the following code:

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

    print(f2(2, 0))



    0
    1
    2
    3

    View Answer | Discuss in forum