Discrete Structures, Logic, and Computability

[bmcutler011]

I was wondering anyone knew how to figure these problems out.
To, me it is hard and I really need this done by Sunday morning. If possible please reply, thanks!

1. Construct a recursive definition , where all variables are natural numbers.

f(n, k) = k + (k + 1) + (k + 2) + ... + (k + n).

2. Construct a recursive function definition for the following string functions for strings over the alphabet {a, b}.

f(x) = x, y, where y is the reverse of x.

3. Construct a recursive definition for each of the following functions that involve lists. Use the infix form of cons in the recursive part of each definition. In other words, write h ::t in place of cons(h,t).

(1, n = subscripts)
f(a, (<x1, y1),...(xn, yn)>) = <(x1 + a, y1), ..., (xn + a, yn)>

[Rashakil Fol]

Do you understand what recursive definitions are? The recursive definitions for 2 and 3 should come quite naturally.

1. Construct a recursive definition , where all variables are natural numbers.

f(n, k) = k + (k + 1) + (k + 2) + ... + (k + n).

Hint: f(n, k) = [k + (k + 1) + (k + 2) + ... + (k + (n - 1))] + (k + n)

2. Construct a recursive function definition for the following string functions for strings over the alphabet {a, b}.

f(x) = x, y, where y is the reverse of x.

Devise any means to break the string into substrings, and the recursion should be the obvious.

3. Construct a recursive definition for each of the following functions that involve lists. Use the infix form of cons in the recursive part of each definition. In other words, write h ::t in place of cons(h,t).

(1, n = subscripts)
f(a, (<x1, y1),...(xn, yn)>) = <(x1 + a, y1), ..., (xn + a, yn)>

Your recursive call will be on the tail of the list. (What else could it possibly be on?)

[bmcutler011]

it helped me a little but not really. is there anyone to help me step by step process of these problems. please?

[Rashakil Fol]

Look at your examples in class or your textbook, it should follow the same pattern...

[bmcutler011]

The book totally sucks!
I am just being honest.

[Rashakil Fol]

Well here's another hint. In general, recursive functions on lists follow the form

f(nil) = baseCase
f(h :: t) = g(h, f(t))