Solving Recursion & Strings Problems

In summary: This will give the correct answer for n>=3.In summary, Opalg suggests that the recurrence for tn that holds for all n 3 is $t_n=t_{n-1}+2t_{n-2}$.
  • #1
delc1
9
0
Hi all,

I cannot understand how to do the following question from a practice test paper and urgently need help!

For each integer n >=1, let tn be the number of strings of n letters that can be produced by
concatenating (running together) copies of the strings
'a", "bc" and "cb".
For example, t1 = 1 ("a" is the only possible string) and t2 = 3 ("aa", "bc" and "cb" are the
possible strings).
(a) Find t3 and t4.
(b) Find a recurrence for tn that holds for all n  3. Explain why your recurrence gives tn.
(You do not have to solve the recurrence.)
 
Physics news on Phys.org
  • #2
delc1 said:
Hi all,

I cannot understand how to do the following question from a practice test paper and urgently need help!

For each integer n >=1, let tn be the number of strings of n letters that can be produced by
concatenating (running together) copies of the strings
'a", "bc" and "cb".
For example, t1 = 1 ("a" is the only possible string) and t2 = 3 ("aa", "bc" and "cb" are the
possible strings).
(a) Find t3 and t4.
(b) Find a recurrence for tn that holds for all n 3. Explain why your recurrence gives tn.
(You do not have to solve the recurrence.)
Hi delc1 and welcome to MHB!

Have you been able to make any progress with this problem? For example, in part (a) you are asked to find t3, which is the number of strings of length 3 formed from the ingredients "a", "bc" and "cb". Have you tried to write down all such possible strings? (There are not many, so write them all down and then count how many there are. Then do the same for strings of length 4.)

For part (b), there are two ways to construct a string of length $n$. You can take a string of length $n-1$ and add an "a" at the end of it. Or you can take a string of length $n-2$ and add either a "bc" or a "cb" at the end of it.
 
  • #3
Opalg said:
Hi delc1 and welcome to MHB!

Have you been able to make any progress with this problem? For example, in part (a) you are asked to find t3, which is the number of strings of length 3 formed from the ingredients "a", "bc" and "cb". Have you tried to write down all such possible strings? (There are not many, so write them all down and then count how many there are. Then do the same for strings of length 4.)

For part (b), there are two ways to construct a string of length $n$. You can take a string of length $n-1$ and add an "a" at the end of it. Or you can take a string of length $n-2$ and add either a "bc" or a "cb" at the end of it.

Thank you! Appreciate the help. I understand what is being asked now.
 
  • #4
hello, sorry to revive the thread but I am looking at the question and can't make a recursive function for n \ge 3 to save me. I think it has something to do with the n-1 for "a" and n-2 for "bc" and "cb". obviously it has something to do with the previous cases as it is a recursive function. any extra help or hints you could provide would be helpful.

tl;dr do you have any other tips for this question?
 
  • #5
Using Opalg's idea, $t_n=t_{n-1}+2t_{n-2}$.
 

FAQ: Solving Recursion & Strings Problems

What is recursion and how does it work?

Recursion is a programming technique in which a function calls itself repeatedly until a base case is reached. This allows for complex problems to be broken down into smaller, simpler subproblems, making them easier to solve.

How do I approach solving recursion problems?

The key to solving recursion problems is to first identify the base case, as well as the recursive case. The base case is the simplest version of the problem that can be solved directly, while the recursive case involves breaking down the problem into smaller subproblems. Once these are identified, you can then write a recursive function that calls itself to solve the subproblems until the base case is reached.

What are some common mistakes when solving recursion problems?

One common mistake is forgetting to include a base case, which can lead to an infinite loop. Another mistake is not properly understanding the problem and not identifying the recursive case correctly. It is also important to make sure that the recursive function is making progress towards the base case, otherwise it may also result in an infinite loop.

How do strings relate to recursion?

Strings can be thought of as a special case of recursion, where each character in the string can be thought of as a subproblem. Many problems involving strings can be solved using recursion, such as reversing a string or finding all permutations of a string.

Are there any tips for optimizing recursive solutions?

One tip is to use memoization, which is a technique for storing previously calculated values in order to avoid repeating unnecessary calculations. You can also try to think of ways to reduce the number of recursive calls or use iterative approaches instead. It is important to also understand the time and space complexity of your recursive solution in order to optimize it.

Similar threads

MHB Can You Define the Recursive Equation for Strings of 1s and 2s with 3 Mod 4 1s?
Replies
1
Views
1K
MHB Find a recursive formula for the number of combinations
Replies
3
Views
2K
Comp Sci Complexity for generating strings of length k from CNF grammar
Replies
3
Views
1K
MHB Solve Recurrence: $s_n = 2_{s_n-1} - s_{n-2}$ | Discrete Math
Replies
2
Views
2K
Comp Sci Validating Braces Placement for Expression Evaluation
Replies
10
Views
2K
A "The Operation Combination Problem"
Replies
2
Views
1K
Mathematica Numerically solve recurrence relation
Replies
5
Views
2K
MHB Proving Ackermann's Function is Not Primitive Recursive
Replies
1
Views
2K
I Ways to put n balls in m boxes such that exactly k boxes are empty?
Replies
29
Views
513
What Happens to the Tensions in a Cut String Problem?
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top