I really need help with this task here. Im stuck at it and I really would appreciate your help

Here is the task:

Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and $r(moro) = orom$. (given that $A$ the amount of letters in the Norwegian alphabet which has 29 letters.). Define the function in such a way that it is correctly regardless of what $A$ are.

Also $logikk$ means $logic$ in norwegian, and $moro$ means $fun$ in norwegian in case you're wondering.


I tried to solve one of the recursive functions, $r(logikk)$, but i'm not sure if all of it is correct:

$\Lambda =$ The empty string

$r(\Lambda) =$ $\Lambda$, $r(k) = k$, $r(k) = k$, $r(i) = i$, $r(g) = g$, $r(o) = o$, $r(l) = l$

For any word $w$ and letter $a$, $r(wa) = wa$

Can someone please check if this is correct for $r(logikk)$ I feel like i'm missing something but i'm not sure what.

  • $\begingroup$ In which way is this a computer science and not a programming question (which should be on Stack Overflow)? (Hint: you can do stuff while descending recursively, and while "coming up".) $\endgroup$ – Raphael Oct 14 '13 at 7:57
  • $\begingroup$ It's an exercise in some computer science course. Can you guess which, and how theoretical the course is? $\endgroup$ – Yuval Filmus Oct 14 '13 at 16:59

A recursive function requires base cases and recursive rules. Depending on how your system works, your base cases might include:

  • $r(\lambda) = \lambda$
  • $r(\sigma) = \sigma$ for $\sigma \in \Sigma$
  • etc.

You then need a general rule for more complicated cases. You're on the right track; you need a rule that takes something of the form $\sigma w$, where $\sigma \in \Sigma$ is a single letter and $w \in \Sigma^*$ is some arbitrary string, and produces the correct output. You will likely find, and should try to prove, that a rule like the following works:

  • $r(\sigma w) = w \sigma$

Fits the bill. Putting it all together, in pseudocode, you should arrive at something roughly like the following:

1. if n = 0 then return the empty string
2. else if n = 1 then return string[1]
3. else return the concatenation of Reverse(string[2...n]) with string[1]

Hint: Distinguish between two cases: the input is a single letter $\alpha$, and the input is a word $w = \alpha x$ (where $\alpha$ is a letter). In the first case, $f(\alpha) = \alpha$. What can you say in the second case? (For example, consider $w = logikk$, $\alpha = l$, $x = ogikk$.)

  • $\begingroup$ could you please check my edit on the post and check if i'm in the right direction? $\endgroup$ – Dabbish Oct 13 '13 at 20:48
  • $\begingroup$ I'm afraid your answer is meaningless. You should write a function $r$ that on input $w$ outputs the reverse of $w$. You can check you definition to see if it indeed gives $r(logikk) = kkigol$. Also, I don't see why you need to define $r(k) = k$ twice, and why you can't just define in general $r(x) = x$ for any symbol (letter) $x$. Finally, you are confusing variable names and strings. Your function should really satisfy $r("logikk") = "kkigol"$, where "..." indicates a string. $\endgroup$ – Yuval Filmus Oct 14 '13 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.