Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Help!!!(Anyone that truly understands recursion)

Posted on 2003-03-02
3
Medium Priority
?
190 Views
Last Modified: 2010-04-17
This was a question from my lab at class.  It's over, but I still don't quite understand it.  They say if I can understand this question I know recursion.  can someone please explain how this works.

Provided below is a function.  Simply stick it in main and have an int passed into it and the fun begins.

void f(int n) {
   if (n > 1) {
      cout << 'a';
      f(n/2);
      cout << 'b';
      f(n/2);
   }
   cout << 'c';
}

The function output of the code is easy when the numbers passed into is 1,2, or 3.  However, I get losts when it starts going to 4.  If anyone can help me please tell me the output of this code when a 4 is passed into the funciton.  If you can please tell me how you got it.  If possible explain with values of 5,6,7 as well.  Thank You.
0
Comment
Question by:Hailfire
3 Comments
 
LVL 85

Expert Comment

by:ozo
ID: 8054090
1       c
2       acbcc
3       acbcc
4       aacbccbacbccc
5       aacbccbacbccc
6       aacbccbacbccc
7       aacbccbacbccc
8       aaacbccbacbcccbaacbccbacbcccc
0
 

Accepted Solution

by:
BlueTrin earned 200 total points
ID: 8054118
Um this program is recursive in the sense that it calls itself with the value n/2.

I'll try to simplify the way you can get the value of f(n) for a certain value of n:

-------------------- THEORY ---------------------

So for another value than '1':

The function :
 - 1 - prints 'a'
 - 2 - then calls itself but with the value n/2
 - 3 - prints 'b'
 - 4 - then calls itself but with the value n/2
 - 5 - prints 'c'

Basically the output is :
'a'
Output for the value n/2
'b'
Output for the value n/2
then 'c'

-------------------- EXAMPLES ---------------------

So if we call Output (n) the output for the value n, for the value n=2, we have:

Output (n=2) = 'a' + Output(1) + 'b' + Output(1) + 'c'
Output (n=2) = 'a' + 'c' + 'b' + 'c' + 'c'
Output (n=2) = 'acbcc'

Output (n=3) = 'a' + Output(1) + 'b' + Output(1) + 'c'
Output (n=3) = 'a' + 'c' + 'b' + 'c' + 'c'
Output (n=3) = 'acbcc'

Output (n=4) = 'a' + Output(2) + 'b' + Output(2) + 'c'
Output (n=4) = 'a' + 'acbcc' + 'b' + 'acbcc' + 'c'
Output (n=4) = 'aacbccbacbccc'


i m sure you can figure the values for greater values yourself using this method ^_^
0
 

Author Comment

by:Hailfire
ID: 8147765
Thank you BlueTrin for your help.
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
Screencast - Getting to Know the Pipeline

577 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question