2.8 Recursive definitions

Recursive algorithms

An algorithm is a sequence of steps, including at least 1 terminating step, for solving a problem. A recursive algorithm is an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.

Because a problem cannot be endlessly divided into smaller subproblems, a recursive algorithm must have a base case: A case where a recursive algorithm completes without applying itself to a smaller subproblem.

Activity 1: Recursive algorithms.

  1. A recursive algorithm applies itself to a smaller subproblem in all cases.
    True
    False


  2. The base case is what ensures that a recursive algorithm eventually terminates.
    True
    False


  3. The presence of a base case is what identifies an algorithm as being recursive.
    True
    False


Recursive functions

A recursive function is a function that calls itself. Recursive functions are commonly used to implement recursive algorithms.

image1

Activity 2: CumulativeSum recursive function.

  1. What is the condition for the base case in the CumulativeSum function?
    N equals 0
    N does not equal 0


  2. If Factorial(6) is called, how many additional calls are made to Factorial to compute the result of 720?
    7
    5
    3


  3. Suppose ReverseList is called on a list of size 3, a start index of 0, and an out-of-bounds end index of 3. The base case ensures that the function still properly sorts the list.
    True
    False