I am not good at recursive functions and I was wondering if anyone had any tips or examples I could do to get better at it. Right now I am programming in C++ for a class I am taking and would like to get better at it in that language.
Try scheme or haskell.
In scheme and haskell the only way to loop is to use recursion.
Read about tail recursion and understand it.
Also, why recursion? Don't use recursion in C++ unless it is the only way.
Forcing recursion where iteration is more logical is silly, and is one reason I'm not too fond of functional programming.
No, what >>1 wants to do is study recursive functions in actual use. Certain algorithms become much easier when implemented recursively, just as others are much easier when implemented iteratively. So to learn properly about recursion, study those cases where it is useful.
Of course, now that I said that I can't think of any good and simple examples off the top of my head. Most of the basic examples of recursion tend to be things which work better iteratively, which makes the whole thing pretty pointless.
I guess traversing trees might be a decent example, but I don't have anything good to link to. So I'll leave the specifics to someone else.
>>3
Try to write the fibonacci algorithm iteratively.
The recursive approach is simple
[code]
/* C */
int fib(int n) {
if(n == 0) return 0;
else if(n == 1) return 1;
else return fib(n-1) + fib(n-2);}
; scheme
(define (fib n)
(cond ((= n 0) 0)
(= n 1) 1)
(else (fib (- n 1) (- n 2))))))[/code]
Figuring out how to write it iteratively is not that easy, try it :D
Also, they are not 'forcing' recursion.
Recursion can be the same with iteration if written properly.
(ie where tail-call optimization is possible)
>>4
Ah crap, I forgot about wakabamark
Why is it that whenever recursion comes up, someone invariably gives a terrible fibonacci implementation?
A much more practical example would be directory traversal in a filesystem. Take a quick look at the opendir and readdir functions, and try making a program that finds all the files in a directory and all subdirectories.
Here's a bit of code to get you started:
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>int isdirectory(char *f) {
struct stat s;
return stat(f,&s) == -1 ? 0 : S_ISDIR(s.st_mode);
}and for reading the directories themselves,
DIR *d;
struct dirent *e;
char *dirname;
d = opendir(dirname);
while ((e = readdir(d))) {
// do stuff with e->d_name here
}
closedir(d);> Figuring out how to write it iteratively is not that easy, try it :D
int fib(int n)
{
int a = 1, b = 0, t;
while (n-- > 0) {
t = b;
b += a;
a = t;
}
return b;
}That took me like ten seconds and worked on the first try.
Seriously, Fibonacci and factorials where exactly what I was referring to when I was saying that "Most of the basic examples of recursion tend to be things which work better iteratively".
That recursive fibonacci implementation is horrible, too. It runs in, what, exponential time? It's exactly that kind of shit that nobody should teach, ever.
To understand recursion, you must first understand recursion.
A recursive haskell fibonacci function that runs in linear time:
[code]fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))[/code]
ta da!
And is also entirely opaque.
Is haskell supposed to remind me of forth?
>>13
It hurts your brain about as much when you're trying to learn it.
As wacky was Forth is, it's nowhere near Haskell.
>>10
a javascript fibonacci function that runs in constant time:
function fib(n){
var p=Math.sqrt(5);
return (1/p)*(Math.pow((1+p)/2,n)-Math.pow(2/(1+p),n)*Math.cos(n*Math.PI));
}>>16 That's very clever. It seems to lose accuracy around fib(72). More accuracy means adding more accuracy to PI, and that means you'd need a constant-time function to find bits of PI.
I do notice that the CL version has fewer "parens" (braces, semicolons, etc) than the C version >>6 wrote.
(defun fib (n)
(loop repeat n
with p = 0 and q = 1
do (psetq p q q (+ p q))
finally (return p)))> More accuracy means adding more accuracy to PI, and that means you'd need a constant-time function to find bits of PI.
Even fetching the precomputed value from a web server won't be constant as the time it takes to download the bits will be linear with the number of bits you need to download.
what?
>>19 I thought it was pretty easy to understand. Maybe you need to read it again?
>>20
I don't think constant-time and linear-time mean what I think you think they mean.
constant-time: takes the same amount of time no matter what the request is.
linear-time: takes an amount of time which is some constant times the size of what was requested.
For example, storing 8GB of Pi on a server as part of a script and returning the whole thing even if the user only needs the first 4 bytes -- that's constant-time. Nobody every said it had to be fast, just constant.
>>24
and a lookup table for e^x, too
>>1
A helpful tip is that it's almost always best to establish the stopping condition before working on the rest.
Read SICP.
No, I'm not trolling. Seriously, thinking "I'm using C++, so I should learn recursion using this language" is dumb. Learn recursion properly using a language that properly supports it, then once you mastered the concepts, you'll be able to do it in another language just fine.
>>27
Op here,
I didn't think "I am learning C++, so I should learn recursion" it was more like "I am taking a class on C++ and they want me to do recursive functions but I am so shitty at them. I wounder if there is anything I can do to improve that".
>>9
Thank you for your help. I looked into it more and I got a better understanding of it and was able to write better recursion code.
>>28
wonder
>>1
If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is.
>>31
If you don't mind that even tail recursion can blow the stack.
>>32
All the good implementations implement tail calls without using the stack (if you enable optimizations)..
Most C/C++ compilers that implement some kind of tail-call optimization (TCO) will refuse to do it for a large number of cases, including some of these:
&)alloca() (or a C99-variable-sized array)setjmp() or exceptionsIt's funny: The same people who worry about stack smashing are the same people who try and recover when malloc() returns NULL.
>>34 you're a fucking n00b. just shut the fuck up since you obviously haven't read shit about those languages god dammit.
> Taking the address-of a stack allocated variable (using &)
There are no stack allocated variables. There are automatic objects. You're wrong, since conceptually this doesn't allow for tail-call recursion;
You presumably have something like this in mind,void foo(int *p) { int i; if(*p <= 0) return; i = *p - 1; foo(&i); }
Whether you realize it or not, there is an operation after foo(&i); (the destruction of 'i' that other functions depend on it), so technically, this is not tail-call.
> If you use alloca() (or a C99-variable-sized array)
alloca() is not standard. You fucking moron blockhead.
I'm curious, have you read the semantics of C99 vlas? You most likely invoke undefined behavior where you don't realize it.
Undefined behavior == broken code.
Broken code == the compiler/implementation is allowed to do anything.
> If you're using Visual C/C++ version 8.1 or earlier
Hint: VC is a piece of shit.
> If the number of arguments changes (sometimes!)
Explain.
> If it's an indirect function call
Again, explain.
> If any of the types change the ABI needed (int->float, etc)
Nonsense.
Tl;dr go read the fucking standards (ISO 9899:1999, ISO 14882:2003), then go read some CS documents on recursion. You fucking imbecilic piece of shit.
I understand you think you know more about C and how C compilers are implemented than you actually do. I'll explain the one you had the most trouble with, but this is extremely time consuming and I won't want to waste my time if you're just going to fag it up with more hostility.
extern int baz(int *z);
static void foo(int x) {
if (baz(&x) <= 0) return;
foo(x-1);
}
void bar(int x) {
foo(&x);
}GCC produces:
It should look something like this:
This is tail recursive, and the reason gcc fails to eliminate the recursive call because of the &. Remove it and you'll see GCC can eliminate it just fine (even though the resulting logic is wrong).
There's no reason gcc can't optimize alloca() away for similar reasons, or if the tail-call involves two (mutually cooperating) functions when the number of arguments changes.
You should not write code assuming gcc can optimize it, if you don't know it will. Disassemble it's output, and verify it did. Comment that your logic expects this behavior.
You also should be careful when calling anyone a "fucking imbecilic piece of shit".
You're clearly very new at this programming thing, and the more time you spend talking to other people on the subject, the more likely it is you're going to run into people who understand this a whole helluva lot better than you do.
Why exactly do you think baz relevant?
The disassemblies demonstrate that it isn't. Check for yourself; gcc will not tail-recurse any function that takes the address of a stack allocated variable (using &).
>>39
there is no such thing as a "stack allocated variable" in c.
Now I know you're not telling me that you think "baz" is relevant because there is no such thing as a "stack allocated variable" in the C standards.
There is however, such a thing as a "stack allocated variable" in gcc. When we are talking about tail-recursion optimizations which are a feature of implementations of C, we are not talking of the C language itself.
Review >>33 where we had:
> All the good implementations implement tail calls without using the stack (if you enable optimizations)..
And >>34 disagreed. Not all good implementations implement tail call (elimination) in every possible case- or even every obviously possible case.
>>41
God dammit you fucking blockhead fucking shit fuck.
First, I'm not >>40. I'm the other guy swearing. Anyway, God dammit baz is relevant because you fucking call it in your code you fucking shit fuck.
the fuckin definition is not provided. Instead you provide the definition of bar.
> There is however, such a thing as a "stack allocated variable" in gcc.
Wrong.
Look, you suck. I'm a C cognoscente and I don't expect anyone who disagrees with me to be correct.
> Not all good implementations implement tail call (elimination) in every possible case- or even every obviously possible case.
I have explained why those cases that seem obvious, are NOT cases where tail-call optimization can be applied.
It's because of semantic minutiae, apparently lying in that knowledge lacuna of yours.
> baz is relevant because you fucking call it
The external call to baz is to prevent gcc from eliminating the take-address-of operation. It demonstratedly has no bearing on tail-call elimination; gcc will (for example) optimize the tail call on this code:
extern int baz(int *z);
static void foo(int x) {
if (baz((int*)x) <= 0) return;
x--;
foo(x);
}
void bar(int x) {
foo(&x);
}> I'm a C cognoscente and I don't expect anyone who disagrees with me to be correct.
However, you're still wrong. Being a C connoisseur means you can appreciate C. It doesn't mean you know C; it doesn't mean you know C implementations. In fact it's clear that you don't know C or gcc very well at all.
> I have explained why those cases that seem obvious, are NOT cases where tail-call optimization can be applied.
No, you haven't. You have simply declared it so, done some handwaving about C not having stack variables, and then ate a thesaurus.
You're still wrong.
Your code is invalid.
Line 3, you convert an integer to a pointer.
Not only this is meaningless, but see 6.3.2.3 Pointers paragraph 5.
> An integer may be converted to any pointer type. Except as previously specified, the
> result is implementation-defined, might not be correctly aligned, might not point to an
> entity of the referenced type, and might be a trap representation.
Your code invokes undefined behavior. You've failed. You can no longer act like you know C. Just shut up. Go read the current C standard.
> However, you're still wrong. Being a C connoisseur means you can appreciate C. It doesn't mean you know C; it doesn't mean you know C implementations.
I said cognosente. Not conneisseur. Regardless, being a C cognosente means you both appreciate the semantics and you're highly specialized, ie an expert.
C has nothing to do with C implementations. I have, however, read Plaugers book, and have read many bits from glibc.
> C has nothing to do with C implementations.
But tail-call optimization does have something to do with implementations. >>33 was asking about implementations.
You think anyone cares what you think about something that nobody on this thread was talking about?
Grow up.
Nobody wants to be your friend, and nobody wants to talk to you because when someone asks a question about something you don't know anything about, you stamp your feet and cry and scream about something you do know something about.
> Your code is invalid. Line 3, you convert an integer to a pointer. Not only this is meaningless, but see 6.3.2.3 Pointers paragraph 5.
See >>33 for a reminder on just how irrelevant your statement is.
> Your code invokes undefined behavior.
You invoke undefined behavior. I know exactly what gcc will do because I looked at it's disassembly. In case you've forgotten already, this thread is about an implementation detail of C compilers, not about you.
> I said cognosente. Not conneisseur. Regardless, being a C cognosente means you both appreciate the semantics and you're highly specialized, ie an expert.
M-w, the oed, and wordnet all disagree with you.
> > I said cognosente. Not conneisseur. Regardless, being a C cognosente means you both appreciate the semantics and you're highly specialized, ie an expert.
> M-w, the oed, and wordnet all disagree with you.
What a terrible liar you are
M-w (first I thought you talked about emacs)
http://www.merriam-webster.com/dictionary/cognoscente
Quote:
> a person who has expert knowledge in a subject
Wordnet
http://wordnet.princeton.edu/perl/webwn?s=cognoscente
> cognoscente (an expert able to appreciate a field; especially in the fine arts)
JUST HOW THE FUCK DID THOSE DISAGREE WITH ME?
As for oed, it's an unusable piece of shit, I'm unable to locate the search field.
From M-w:
> cognoscente: a person who has expert knowledge in a subject : connoisseur
From wordnet:
> cognoscente: (n) connoisseur, cognoscente (an expert able to appreciate a field; especially in the fine arts)
....
> I said cognosente. Not conneisseur
Both of these sources that you accepted say cognoscente is a synonym for connoisseur.
> JUST HOW THE FUCK DID THOSE DISAGREE WITH ME?
In m-w, look directly after the part that you quoted. In wordnet, look directly before the part you quoted.
Anyway, this is getting silly, and you're looking more and more ridiculous every time you reply; You're clearly not an expert of C or C implementations, and I don't think you're an expert of jack or shit either.
Would each of you kindly take the other's dick out of your mouth
> You're clearly not an expert of C or C implementations,
Bullshit, I am. Ask any C question.
> It didn't.
Of course it does. If I don't have the definition, how will I be able to answer what happends in baz(&z)?
You're a retard. Have you even noticed that the function is named BAZ and you give the definition of a function named BAR that never gets called?
GOD DAMMIT YOU MORON.
> Of course it does. If I don't have the definition, how will I be able to answer what happends in baz(&z)?
Nobody asked what happens in baz- not even gcc. That means that the definition doesn't matter.
baz(&z) cannot do something with the address of z that would be valid with a tail call, that would be invalid were the tail-call eliminated.
> you give the definition of a function named BAR that never gets called?
Of course! If foo isn't static, some versions of gcc wouldn't eliminate the tail call of foo within foo()'s body even when & isn't being used. If foo weren't called by a non-static function, gcc wouldn't even have to emit the definition of foo.
You seem to have forgotten the point of the exercise was to demonstrate how a single & is enough to throw off gcc's ability to eliminate an otherwise obvious tail-call.
The source-example was something simple, that anyone can pipe into gcc -S and see exactly when gcc actually performs tail-call optimization, and when it doesn't.
I just don't care anymore. If you want tail recursion use a language whose standard requires it.
> If you want tail recursion use a language whose standard requires it.
what if i want to use some tail recursive functions and some recursive functions that aren't tail recursive?
>>54
just use them. any more questions?
Profile it if you suspect it's going to be a problem. It's not that hard- >>36 covered most of the details.
Simply gcc -S -c chunk.c and look at the chunk.s output -- if you see a nested call at the end of your function, gcc didn't eliminate that tail call.
If you think it should, play with the optimizations and/or try and remove anything >>34 listed. If you can't get gcc to do eliminate the tail-call, rewrite the tail-recursion with a loop.
>>54
Do I just not know progrmming enought or is that the most stupidest question ever?
>>57
it was stupid on purpose, to point out the stupidity of the statement it was in reply to.