Purchase Solution

Recursive definition

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

Solution Summary

This is a proof regarding recursive definitions and integers.

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 ...

Purchase this Solution


Free BrainMass Quizzes
Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.