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
Exponential Expressions

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

Solving quadratic inequalities

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

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Probability Quiz

Some questions on probability

View More Free Quizzes
Related BrainMass Solutions

  • Recursive definitions

    22819 Recursive definition I need to give a recursive definition with initial condition(s). a.) The sequence {an}, n = 1,2,3,... where an = 2n. b.)

  • Recursive definitions

    This solution is comprised of a detailed explanation to give a recursive definition.

  • Recursive Algorithm

    So, the first step for coming up with your algorithm is to write the recursive definition of the sequence you need.

  • Choose an iterative procedure to re-write as recursive

    I have chosen to rewrite the iterative definition of calculating factorial of a number using a recursive procedure. First, the iterative definition of factorial is as follows For any non-negative integer n, the factorial of n , denoted n!

  • How to Convert a Recursive Procedure into Iterative

    The Fibonacci sequence is a popular example of recursion[3]: [base cases] Fib(0) is 1 Fib(1) is 1 For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition] We can write a simple C code snippet for this definition.

  • Definitions : Sequence, Geometric Progression, String, Recursive

    Recursive definition of a function 5. Recursive definition of a set 6. Recursive algorithm 7. Program correctness 8. Loop invariant 9.

  • Recursive definitions

    This solution is comprised of a detailed explanation to give a recursive definition.

  • Theory of Computation with a Vending Machine

    Give an implicit definition of the set of all strings whose value mod 30 = 0. 2. Give recursive definition of the set of all strings whose value = 30 cents. See attachment for the full and formatted problem. Please see attached file.

  • Writing a recursive algorithm

    = 1 by definition, we can show that C(n,0) = 1 = C(n,n) Also, C(n,r) = C(n-1, r-1) + C(n-1, r) Given the information above, write a recursive algorithm to find C(n,r) for any two non-negative integers n and r, with r <= n The recursive algorithm

View More Related Solutions