Explore BrainMass

Explore BrainMass

    Recursive definition

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    We can define sorted lists of integers as follows:

    Basis - A list consisting of a single integer is sorted.

    Induction - If L is a sorted list in which the last element is a and if b >= a, then L followed by b is a sorted list.

    Prove that this recursive definition of "sorted list" is equivalent to our original, nonrecursive definition, which is that the list consist of integers

    a1 <= a2 <= .... <= an

    Remember, you need to prove to parts:

    (a) If a list is sorted by the recursive definition, then it is sorted by the nonrecursive definition

    (b) if a list is sorted by the nonrecursive definition, then it is sorted by the recursive definition.

    Part(a) can use induction on the number of times the recursive rule is used, and (b) can use induction on the length of the list.

    © BrainMass Inc. brainmass.com February 24, 2021, 2:30 pm ad1c9bdddf

    Solution Preview

    (a) Recursive => Non-recursive
    Prove by induction:
    Let a list{a_1,a_2,a_3,...a_n}be a sorted list defined by the recursive definition.
    (1) Let L_1=a_1, and the last element is a_1, which is sorted. Followed by a_2, satisfying a_1<=a_2, therefore L_2= {a_1,a_2},satisfying a_1<=a_2, which is sorted by the non-recursive ...

    Solution Summary

    This is a proof regarding recursive definitions and integers.