?
Solved

Help!!!(Anyone that truly understands recursion)

Posted on 2003-03-02
3
Medium Priority
?
189 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 84

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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
Suggested Courses

752 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