Recursion in Recursion in Recursion...

The "end condition" which you mentioned is quite vital, and it depends upon what sort of mathematical equation (or other process) you're trying to perform. For an example, I'll write a function that finds the factorial of a number.


And if you were to pass 5 to that function, the process would go something like this:

total = 5 * ((5 - 1) * ((4 - 1) * ((3 - 1) * ((2 - 1)) = 120;

Hopefully that little demonstration will help... If you don't understand how it works, though, look up some resources, or just run through the example step by step and remember that there are a bunch of imbedded levels and whatnot, all of which have their own local variables and stuff. I don't know what else to say...

[Edited by - Omega147 on April 13, 2006 4:08:52 PM]

Sounds worse than Ackerman's function

I think you simply have to learn how to convert recursive functions into iterative ones. For example, could you convert a recursive version of the factorial function into its iterative form?

Quote:

Original post by iMalc I think you simply have to learn how to convert recursive functions into iterative ones. For example, could you convert a recursive version of the factorial function into its iterative form?

Yes, the factorial function could also be written as:


But there are good and bad reasons to writing a function as recursive or iterative. Anyone want to point out the major differences? I'm at work... lol

If the recursion is the last call in the function, it is 'tail recursion', and on any modern compiler is equivilant to the iterative form. Furthermore, for some problems, the recursive solution is simpler, more elegant, and easier to understand. Some people just can't seem to understand recursion, though. These people should not be computer programmers.

Quote:

Original post by Deyja Some people just can't seem to understand recursion, though. These people should not be computer programmers.

Hehe. Agreed!

I don't understand what it is you want to do here. If the recursive call doesn't change anything then it will recurse infinetly... so what is the difference between your function call and this:

while(true) {
5
}

???

L-

See also Church numerals...

Wow none of you guys answered my question. Im not asking what recursion is. Im asking how would I make a recursive function, that calls it self as the parameter...repeatedly?

so it would be like:
f(x) = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(

and never end. Isnt there a way to make it end? Isnt there a way to tell the compiler/interpreter to constantly call f(f(f(f(.. and so on as the parameter? I think its pretty interesting to think about, but I dont know of any ways to do it in C++ but im not sure of other languages like Haskell or even just math equations. Its got to be possible.

EDIT: This is a super simple example, in a real solution it would have a condition to stop, but im not worried about that so im just showing you the problem.

EDIT 2: Ive already read about factorials, ackerman's, fibonacci, ect ect and as far as I can tell, this problem has nothing to do with them.

If you want to pass an actual function as the paramater, look into void* ~ that what you're asking for?

Is that would you're trying to do?

-_- I dont see why you guys dont understand this. I want to call a function, call a function for its parameter, then call a function for its parameter, OVER AND OVER AND OVER, nonstop...like I said:
f(x) = f(f(f(f(f( see, f calls f and calling f for the parameter, over and over. Nothing to do with void. This has nothing to do with church's numerials, nothing to do with void, nothing like that. You cant type infinity but how do you make a function that calls a function as a parameter that calls a function as a parmeter for infinity? Only to stop when the condition is met

Translating your recursive parameter idea into the standard form of recursion, you basically end up with a function like this:

int f(){  int r = f();  //do stuff with r  return r;}

The recursion happens before processing. It operates basically by saying: "I don't have a parameter yet, or at least don't have a value for my parameter. I will ask myself for a parameter value, and once I have that value, I will work with it, and return the result." What this ultimately means is that there is no possible terminating condition. Which makes the idea have, as far as I can tell, no practical value.

Compared to tail recursion, I suppose this would actually be head recursion?

Assuming you were not interested in passing in a functor(pointer to a function ) then it seems to that:
The problem isnt that the question isnt being answered, its that the answers are not being seen the way the answerer intended. As I read thro this thread it seems as tho the question is answered.

If you where having the function calling itself and passing its output into its next put thats it simly recusion, as you said you know this so Im not gonna bother typing the explanation. The thing of point here seems to be that if all that F(x) does is call F(f(.... then you where right to begin with that there is no point in doing such a call ...

int F( int iInput )
{
return F( iInput );
}

This lovly function is an infinite loop, there is no way to exit it, save forcing it through an outside means, hitting power after all always stops things. So long as F doesn check on the values or have conditions where it wouldnt call itself you get the problem of an infinite loop.

DEVILS ADVOCATE TIME:
If you where running a multi-threaded program and had a parent monitoring the recursive loop thread and the recursive thread was acting on a global variable they both had access to could the parent not terminate the child at a given time determined within the parent and still access the now modified value that this all mighty F function we keep mentioning had been acting on?

and thnx for the thread always fun to turn your brain into a recursive thinking machine, gotta love headaches ... anyway I hope this helped
... cheers Downer

Still... how about an example... with code that DOESN'T do what you want it to do.

This is what I'm seeing:



L-

Quote:

Original post by Falling Sky -_- I dont see why you guys dont understand this.

you mean like a fold-function?
eg. like here (fold_left / fold_right)?

Quote:

Original post by Falling Sky -_- I dont see why you guys dont understand this. I want to call a function, call a function for its parameter, then call a function for its parameter, OVER AND OVER AND OVER, nonstop...like I said: f(x) = f(f(f(f(f( see, f calls f and calling f for the parameter, over and over. Nothing to do with void. This has nothing to do with church's numerials, nothing to do with void, nothing like that. You cant type infinity but how do you make a function that calls a function as a parameter that calls a function as a parmeter for infinity? Only to stop when the condition is met

void * can be used in conjunction with function pointers.

You end up with something like this:

// This looks ugly as sintypedef void (*func)(void *);void recurse(void *f){	std::cout << "f(";	func fp = static_cast<func>(f);	fp(&recurse);}recurse(&recurse);

This way you get what you want.

Unfortunately, this is the same as:

void recurse(){  std::cout << "f(";  recurse();}

This works, but not till infinity, but only till stack fills up.

The solution has been posted above already, however your recursion will fail if you exceed your stack/stack is full in other words.

If you function does nothing inside it the compiler will optimize it away anyways.

Recursions are often a source for hidden bugs that appear if used by unexperienced programmers.

It almost sounds like he's trying to do something like this:


Where func() is not overloaded... Can't think of a way to do that... lol

Maybe something like this, with a "helper" function:


But in this case, MSVC generates these warnings:

warning C4717: 'func' : recursive on all control paths, function will cause runtime stack overflow
warning C4717: 'func2' : recursive on all control paths, function will cause runtime stack overflow

In which case, Basiror is correct.

You might be interested in combinators / lambda calculus. Specifically, the Fixed-Point Combinator, which is defined as Y(f) = f(Y(f)), which appears to recurse in exactly the way you want.

Thanks Extrarius

But guys, it cant be the same as a while loop calling f() because f is suppose to take the parameter of the last ones return! It isnt the same I dont think, please explain further if im wrong.