Thread: Recursion

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    91

    Recursion

    Problem:
    It should print its local variable and recursive call parameter. For each recursive call, display the outputs on a separate line and add a level of indentation. Do your utmost to make the outputs clear, interesting and meaningful.

    I havent done yet the "separate line and add a level of indentation".

    Code:
    #include <iostream>
    using namespace std;
    
    void factorial( unsigned long ); 
    
    int main()
    { 
    factorial(5);
    } 
    void factorial( unsigned long number ) 
    {         
    	int result;
    	if ( number <= 1 )
    		cout<<endl;
            else                      
    		cout<<number * factorial( number - 1 );
    }
    Error:
    error C2297: '*' : illegal, right operand has type 'void'

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your function doesn't return anything (void), yet you attempt to multiply it by something.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    91
    But using void is appropriate, right?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    But using void is appropriate, right?
    Maybe, but not until you change the function a little more (think of its parameters).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Change void to unsigned long and you will see your desired result
    Double Helix STL

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, not really. Because there isn't actually a return statement. It requires a few more changes than that.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I would not even make this particular function recursive. You can just use a loop to accomplish the same task without all the extra expense to the stack.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by master5001 View Post
    I would not even make this particular function recursive. You can just use a loop to accomplish the same task without all the extra expense to the stack.
    1. The compiler will probably make it non-recursive since it's plain tail-recursion. At least gcc does.
    2. Because recursion is a concept that needs to be understood, and starting with one of the most simple concepts of recursion is a good way to learn how it works. I have written recursive factorial functions in several languages (Pascal, Modula-2, C, C++ [I think], Basic and a couple of assemblers) just for practice.

    There are problems that are MUCH simpler to solve with recursion than otherwise - and then there are problems that are just as easy to solve iteratively, and for REAL programs, that's the right solution then.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Fair enough. I do understand that the teacher is probably just trying to demonstrate how something can be written more clearly with recursion, however I am not too inclined to write something so simplistic as a recursive function even if I went into it knowing for sure the compiler would optimize out the recursive function and replace it with a loop.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by master5001 View Post
    Fair enough. I do understand that the teacher is probably just trying to demonstrate how something can be written more clearly with recursion, however I am not too inclined to write something so simplistic as a recursive function even if I went into it knowing for sure the compiler would optimize out the recursive function and replace it with a loop.
    Agreed. But if you were to explain recursion to a new student, factorial is about the easiest one to use. Fibonacci series is another example, but involves two calls per step, so a bit more complex. Quicksort is an excellent example of something that is much harder to solve without recursion, but also rather complicated.

    Linked list and binary trees are often walked using recursion.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jul 2008
    Posts
    91
    Cant understand it
    Your function doesn't return anything (void), yet you attempt to multiply it by something.
    I thought void doesn't return anything, so it means its wrong to use void?

    Maybe, but not until you change the function a little more (think of its parameters).
    A little more hint. Please.

    Change void to unsigned long and you will see your desired result
    Tried it but it doesn't work.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    cout<<number * factorial( number - 1 )
    uses factorial as one side of the calculation. That is not allowed when factorial is a void function, because "void" can not be multiplied by an integer.

    As an aside, if you do "factorial(10)", it will print 10 numbers, so you probably want to print the result AFTER the function, instead of inside it.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Jul 2008
    Posts
    91
    This is the whole problem:

    (Visualizing Recursion) It is interesting to watch recursion "in action." Modify the factorial function of Fig. 6.29 to print its local variable and recursive call parameter. For each recursive call, display the outputs on a separate line and add a level of indentation. Do your utmost to make the outputs clear, interesting and meaningful. Your goal here is to design and implement an output format that helps a person understand recursion better. You may want to add such display capabilities to the many other recursion examples and exercises throughout the text.

    Code:
     1  // Fig. 6.29: fig06_29.cpp
     2  // Testing the recursive factorial function.
     3  #include <iostream>
     4  using std::cout;
     5  using std::endl;
     6
     7  #include <iomanip>
     8  using std::setw;
     9
    10  unsigned long factorial( unsigned long ); // function prototype
    11
    12  int main()
    13  {
    14     // calculate the factorials of 0 through 10
    15     for ( int counter = 0; counter <= 10; counter++ )
    16        cout << setw( 2 ) << counter << "! = " << factorial( counter )
    17           << endl;
    18
    19     return 0; // indicates successful termination
    20  } // end main
    21
    22  // recursive definition of function factorial   
    23  unsigned long factorial( unsigned long number ) 
    24  {                                               
    25     if ( number <= 1 ) // test for base case     
    26        return 1; // base cases: 0! = 1 and 1! = 1
    27     else // recursion step                       
    28        return number * factorial( number - 1 );  
    29  } // end function factorial
    Am I doing the right thing if I'm using void?

  14. #14
    Registered User
    Join Date
    Jul 2008
    Posts
    91
    Where should I do the modification in main or in the function?

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Ah, ok, so then you would add the code to show what it is doing inside the factorial function.

    You still have to return the result to main tho'.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM