Problem 1
Define the terms a. Recursion b. Iteration c. Infinite recursion d. Recursive helper function
Problem 2
Outline, but do not implement, a recursive solution for finding the smallest value in a list.
Problem 3
Outline, but do not implement, a recursive solution for sorting a list of numbers. Hint: First find the smallest value in the list.
Problem 3
Write a recursive function reverse(text) that reverses a string. For example, reverse("He1101") returns the string "1011eh". Implement a recursive solution by removing the first character, reversing the remaining text, and combining the two.
Problem 4
Outline, but do not implement, a recursive solution for generating all subsets of the set \(\\{1,2, \ldots, n\\}\).
Problem 6
Use recursion to implement a function def find(text, string) that tests whether a given text contains a string. For example, find("Mississippi", "sip") returns true. Hint: If the text starts with the string you want to match, then you are done. If not, consider the text that you obtain by removing the first character.
Problem 6
Write a recursive definition of \(x^{n}\), where \(n \geq 0\). Hint: How do you compute \(x^{n}\) from \(x^{n-1}\) ? How does the recursion terminate?
Problem 7
Use recursion to implement a function def indexOf(text, string) that returns the starting position of the first substring of the text that matches string. Return \(-1\) if string is not a substring of the text. For example, s. indexof ("Mississippi", "sip") returns 6 . Hint: This is a bit trickier than Exercise P11.6, because you must keep track of how far the match is from the beginning of the text. Make that value a parameter variable of a helper function.
Problem 8
Write a recursive definition of \(n !=1 \times 2 \times \ldots \times n\). Hint: How do you compute \(n !\) from \((n-1) ! ?\) How does this recursion terminate?
Problem 8
Using recursion, find the largest element in a list. Hint: Find the largest element in the subsequence containing all but the last element. Then compare that maximum to the value of the last element.
