Sidebar Sidebar
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

macOS Recursive Calls

S

SRossi

macrumors regular
Original poster
May 27, 2009
202
0
Glasgow, Scotland
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
 
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 :)
 
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)
 
lee1210 said:
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)
Click to expand...

You're making his entry level programming class way too complicated :D
 
lee1210 said:
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)
Click to expand...

He should use type double, built in overflow protection!!! :p
 
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
 
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.
 
asciimov said:
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.
Click to expand...

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
 
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
 
SRossi said:
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.
Click to expand...

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
 
lee1210 said:
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
Click to expand...

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
 
dbell said:
He's making sure you are qualified to do his homework for him.
Click to expand...

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
 
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.
 
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?
 
jared_kipe said:
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?
Click to expand...

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.
 
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!
 
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
 
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:
https://forums.macrumors.com/threads/781746/
https://forums.macrumors.com/threads/689019/
https://forums.macrumors.com/threads/659624/
https://forums.macrumors.com/threads/576479/
https://forums.macrumors.com/threads/561251/
 
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.
 
SRossi said:
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.
Click to expand...

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.
 
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.
 
You must log in or register to reply here.
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.
Top Bottom
Back