🔒 Locked

Recursion in Recursion in Recursion...

Started by nolongerhere Apr 13, 2006 at 3:57 PM 25 replies 5.1k views

Original Post

Apr 13, 2006 at 3:57 PM

Ive been messing with math based stuff a lot latly and I came upon something the other day that I couldnt figure out how to do. I dont see another way to do it and there may not be a point to do it even but I kept thinking about it so heres the idea: If you have say... f(x) = f(5) Thats simple, you have a function that calls it self and passes 5 to it. This is useless I know but just stay with me. But lets say I want to call the function, f, inside of its self and for the parameter, I want to call it's self. And for the parameter of that, I want to call the function again, and so on. So now we have: f(x) = f(f(f(f(f(... what when does this end? How do you do this? I want to continuously call a function for the parameter. Now your prob thinking this is useless but ive been thinking about it and if youve got some condition to end, then it could be useful. But how do you do it? Please help and if you dont understand my babbling just say so, ill try to rephrase it.

Omega147

Apr 13, 2006 at 4:08 PM

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.

// compute factorial of 'num'int factorial(int num){    if(num < 0)    {        return(-1); // negative input    }    else if(num == 0 || num == 1) // this is the "ending condition"    {        return(1); // 0! = 1 and 1! = 1    }    return(num * factorial(num - 1)); // recursive call}

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]

iMalc

Apr 13, 2006 at 4:10 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?

Omega147

Apr 13, 2006 at 4:16 PM

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:

int factorial(int num){    if(num < 0)    {        return(-1); // negative input    }    else if(num == 0 || num == 1)    {        return(1); // 0! = 1 and 1! = 1    }        int total = num;        // no recursive calls here    for(int i = num - 1; i > 0; i--)    {        total *= i;    }        return(total);}

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

Deyja

Apr 13, 2006 at 4:20 PM

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.

Omega147

Apr 13, 2006 at 4:25 PM

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

Hehe. Agreed!

Lucidquiet

Apr 13, 2006 at 4:27 PM

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...

nolongerhere

Apr 13, 2006 at 4:39 PM

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.

Omega147

Apr 13, 2006 at 4:52 PM

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

v0dKA

Apr 13, 2006 at 5:00 PM

int f( int param ){     int result = ...;    // Perform voodoo magic here     return f( result );}

Is that would you're trying to do?

nolongerhere

Apr 13, 2006 at 5:01 PM

-_- 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

Agony

Apr 13, 2006 at 5:02 PM

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?

Downer

Apr 13, 2006 at 5:08 PM

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

Lucidquiet

Apr 13, 2006 at 5:10 PM

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

This is what I'm seeing:

void f(int n) {  f(n);}//  Which is equivalent to:while(true) {  n}

L-

maximAL

Apr 13, 2006 at 5:14 PM

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)?

Antheus

Apr 13, 2006 at 5:22 PM

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.

Basiror

Apr 13, 2006 at 5:46 PM

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.

Omega147

Apr 13, 2006 at 6:09 PM

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

int func(int num = func()){    // ...    return(func());}

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

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

int func2();int func(int num = func2());int func2(){    return(func());}int func(int num){    return(func());}

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.

Extrarius

Apr 13, 2006 at 6:42 PM

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.

nolongerhere

Apr 13, 2006 at 7:16 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.