Recursive Calls

Discussion in 'Mac Programming' started by SRossi, Feb 16, 2010.

  1. SRossi macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #1
    Hey all again,

    At Uni we have just started looking at recursive calls and I'm a little baffled by it all.

    What I'm trying to do is figure out the triangular number series just using recursion. I know how to do it:

    Code:
    int triangular(int x) {
      if (x == 0) return 0;
      if (x == 1) return 1;
      
      return x + triangular(x-1);
    }
    But I cannot seem to get the program to print out each number in the list it just seems to always print out the last number usually 1. So could someone be kind-full enough to show how I would get the numbers to print out in order please.

    I'm doing this in C++ but provide code in any language I should be able to decipher it :D.

    Thanks again,

    Stephen
     
  2. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
  3. kyzen macrumors regular

    Joined:
    Feb 8, 2010
    Location:
    Colorado
    #3
    Sounds like you're putting your return before your print statement. Go ahead and post the code you presently have and we can help you work through where your bug is.

    Not many people here will want to just hand you an answer to your homework :)
     
  4. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #4
    x doesn't seem to be unsigned, what happens if it's negative?

    What happens if x is roundabouts of MAX_INT after a few recursions?

    -Lee

    (Note: These don't have to do with printing, just other issues with the code posted)
     
  5. kyzen macrumors regular

    Joined:
    Feb 8, 2010
    Location:
    Colorado
    #5
    You're making his entry level programming class way too complicated :D
     
  6. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #6
    He should use type double, built in overflow protection!!! :p
     
  7. SRossi thread starter macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #7
    Right here's just a small working portion of what I'm doing, I'm not trying to get anyone to do my homework for me I just said that I was looking to figure out how to show the triangular numbers.

    Lee I'm just trying to make a small program to explain to myself how recursion actually works, so I didn't think it needed to be an unsigned int.

    And kyzen your qualifications ARE?

    Code:

    Code:
    #include <iostream>
    using namespace std;
    
    int triangular(int x) {
    	if (x == 0) return 0;
    	
    	return x + triangular(x-1);
    }
    
    int main (int argc, char * const argv[]) {
        int x = 3;
        cout << triangular(x);
        return 0;
    }
    I removed the check to see if x was 1 as I think that its a crucial part to the series.

    I understand that perhaps people think this is easy and that I should figure it out myself but its quite hard to get my head around.

    Thanks,

    Stephen
     
  8. asciimov macrumors newbie

    Joined:
    Jan 31, 2008
    #8
    A few suggestions.
    1) Make x a little larger... say 7.
    2) remove the cout in the main, just call the function.
    3) find a place to do the cout in the function.
     
  9. SRossi thread starter macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #9
    1)3 was an easier number to work with, like it is easy to figure out the number without having to do calculations etc.

    2 + 3)If you do a cout of x in the function it will just print what x is at that time eg. mine goes 321. And the way I was taught was to call the function from main in a cout call to print the number. This is probably wrong but it was the way the lecturer said to use it. And I thought it would suffice for a small program like this.

    Thanks though,

    Stephen
     
  10. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #10
    If all you wanted was the final result (in this case you want a series, not one result...) printing in main would be fine. But that's not what you want. You should store the result of the recursuve call, display it with a cout (and a space, comma, endl, etc) then return it up the chain.

    -Lee
     
  11. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #11
    Exactly what is the problem?

    Why do you think your program isn't showing triangular numbers?

    When I run your code exactly as you posted it, it outputs 6. Since 6 is the triangular number of 3, for your defined function, it seems to me your program is working.

    If you don't see 6, please post what you do see. If you see nothing, then say that.

    If you want to see more than one triangular number output, then you have to calculate and output more numbers.

    As a matter of clarity, you might want to output a newline:
    Code:
    cout << triangular(x) << endl;
    
    Terminal commands I used to compile and run:
    Code:
    g++ triangular.c
    ./a.out
    
     
  12. SRossi thread starter macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #12
    I completely understand now, I have actually no clue as to how I didn't think of making a numbers value equal to the recursive function call. Now that I've read over the code I see where the value is being assigned to the integer when the function is recalled.

    Thanks for the help people :D

    Stephen
     
  13. kyzen macrumors regular

    Joined:
    Feb 8, 2010
    Location:
    Colorado
    #13
    Uh, I fail to see what my qualifications would have to do with anything here, why do you ask?
     
  14. dbell macrumors member

    Joined:
    Jul 11, 2007
    #14
    He's making sure you are qualified to do his homework for him.
     
  15. SRossi thread starter macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #15
    Exactly, for the homework that wasn't actually homweork.

    I made that comment because he was acting as though I'm not allowed to ask a question about something in programming that I don't completely understand.

    Stephen
     
  16. kyzen macrumors regular

    Joined:
    Feb 8, 2010
    Location:
    Colorado
    #16
    I wasn't saying you aren't allowed to ask a question; I was saying people here aren't often keen to simply do other peoples homework for them, and suggested you provide more info so that people could better help you in general.

    I also offered up my input on the potential cause, which turned out to be more or less correct (at least as far as it pertained to only one line being printed).

    So really, I don't see why you're complaining.
     
  17. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #17
    Recursion has its own uses, but this isn't necessarily one of them.
    Iterative solutions should almost always be faster, and possibly easier to understand.

    Do you think it would be easier as an iterative algorithm? Could you write that?
     
  18. whooleytoo macrumors 603

    whooleytoo

    Joined:
    Aug 2, 2002
    Location:
    Cork, Ireland.
    #18
    Yup. If the OP wants to understand recursion better, perhaps a better-suited task might suit.

    How about writing a recursive function/method to output the contents of a folder; delving down into all sub-folders? It might be a good challenge, given it's not something easily done iteratively.
     
  19. Macula macrumors 6502

    Macula

    Joined:
    Oct 23, 2006
    Location:
    All over the place
    #19
    SRossi,

    That seems to me a good start to explore this most fascinating area of algorithm design, recursion.

    The standard introductory example is the calculation of the factorial

    N!=N*(N-1)*(N-2)*…

    but your own exercise is pretty much equivalent in structure to this. So you're on a good track.

    As a next step—if your instructor does not object—you could explore recursive algorithms that utilize "backtracking". The sheer power of recursion is demonstrated much more effectively in those cases. Searching a tree structure is one such example. Another classic is the routine for drawing Hilbert curves. Or a program figuring all possible permutations of a string of characters (e.g. 123, 132, 213, 231, 312, 321). Or, if you're in for a greater challenge, a chess- or backgammon-playing program! Any textbook on algorithm design will dedicate at least one chapter to backtracking, including lots of examples and exercises.

    The exercise you carried out is an excellent start but does not really elucidate important aspects of recursive functions, especially the way local variables behave (placed into and retrieved from a stack). A study of "backtracking" is therefore a natural second step.

    Have fun exploring this fascinating topic!
     
  20. SRossi thread starter macrumors regular

    Joined:
    May 27, 2009
    Location:
    Glasgow, Scotland
    #20
    jared - We have just been looking at Recursion not quite as far as iterative algorithms, although I might get a head start and a have a quick look at them.

    whooleytoo - Sounds quite an interesting idea, would certainly show me how recursion worked completely and in a task that may be needed in a workplace.

    Marcula - Is there any textbooks that you would perhaps advise me to have a look at? Because recursion is one part of programming that I would like to gain a little extra knowledge than what is given in university.

    Thank you everyone for the reply's, I'm going to continue to look into recursion further, hopefully to gain a knowledge of how powerful it can be.

    Stephen
     
  21. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #21
    if you have a strong interest in recursion, it might be worthwhile for you to take a look at a functional language now while your interest is piqued. I like Haskell (i am by no means a master), but Lisp and Erlang are also popular functional languages.

    As for books, this was used to teach one of my courses. I consider this course and its professor to be one of the best I had.
    http://www.cs.utexas.edu/users/misra/Classes.dir/ClassNotes.dir/337.pdf

    There are a few sections on recursion. Note that this tries to bridge theory and practice, so it's not a lot of "how to write recursively in iterative languages".

    While you're at it, read this by the same professor:
    http://www.cs.utexas.edu/users/misra/Speeches.dir/337.pdf

    It is not about programming, per se, but it is one of the most inspirational things i have come across when it comes to an argument for the importance of theory and education in the life of a programmer.

    I also forewarn you to be prepared for some limitations to programming recursively in a language like C, with a fixed stack size in many implementations, and fixed width numerical types. If you do want to do a factorial (which is a nice way to demonstrate recursion, with a result bubbling back up your recursive call stack) note that there is a limit that might be lower than you think re: the size of your operand before your result overflows int, and even long int. Once you get through more trivial examples, be aware of the number and size of your stack-resident variables in your recursive function. Each recursive case will add these to the stack again, and this can quickly overwhelm the size allocated to your programs stack.

    Good luck!

    -Lee

    Here comes a link dump, in case you want to read more of me yammering on about this:
    http://forums.macrumors.com/showthread.php?t=781746
    http://forums.macrumors.com/showthread.php?t=689019
    http://forums.macrumors.com/showthread.php?t=659624
    http://forums.macrumors.com/showthread.php?t=576479
    http://forums.macrumors.com/showthread.php?t=561251
     
  22. Macula macrumors 6502

    Macula

    Joined:
    Oct 23, 2006
    Location:
    All over the place
    #22
    SRossi, lee1210 gave you some very good guidelines, I think.

    I have a personal preference for Niklaus Wirth's "Algorithm's & Data Structures." It's old and somewhat dry, perhaps also surpassed by newcomers in the publishing arena, but I still appreciate that book for its concision and elegance.

    Prolog is a very natural point of entry to recursion. The trouble is that Prolog is very easy if you're new to programming and much harder if you're conditioned to thinking in terms of procedural languages such as C. It requires a certain naturalness of thought, a sort of naivete, that seasoned programmers have usually inhibited in the process of their formation.

    I explored recursion back in the mid-90s using Pascal. But that was a long time ago, and today there are better alternatives. Though I know very little about Haskell, there seems to be consensus that it's great for training in algorithm design.

    Enjoy, and good luck.
     
  23. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #23
    An iterative algorithm is simply doing something a set number of times, or until a condition is met, they probably always have a for/while loop somewhere to control the process.

    The function
    Code:
    void triangle(int in){
    	int count = 0;
    	while (in > 0) {
    		count += in;
    		printf("%d%s",in,(in>1)?" + ":" ");
    		in--;
    	}
    	printf("= %d\n",count);
    }
    
    Performs your needs for the triangle number number function in C. It is iterative because it does the same thing over and over without pushing more function calls every time.
     
  24. autorelease macrumors regular

    Joined:
    Oct 13, 2008
    Location:
    Achewood, CA
    #24
    A function whose last instruction is to call itself is called tail recursive. Factorial is a good example of a tail recursive algorithm.

    What's special about tail recursive functions is that they can be very easily converted to iterative versions, saving stack space and function call overhead. In fact, compilers for several languages (including GCC) can perform tail call optimization, and automatically compile tail-recursive functions into faster, iterative chunks of code.
     

Share This Page