Jump to content

  • Log In with Google      Sign In   
  • Create Account


Is any recursive function can be translated into its iterative form?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 Triad_prague   Members   -  Reputation: 136

Like
0Likes
Like

Posted 07 December 2011 - 09:50 PM

Hi, I just finished writing a simple scripting system for EDUCATIONAL purpose...it's like a C-language to be honest....
I've tested it and the features (loop(while), user defined function, etc etc) are working fine. however...if a user make a function that calls itself (recursive), it won't return the right result. I'm thinking of ignoring it since (from what I read in a C++ book) "any recursive function can be translated into iterative form".

I wonder....if it's TRUE? I never coded too much recursive function so I can't say ... so please guys, can anyone confirms what that book said?Thanks beforehand :D
the hardest part is the beginning...

Sponsor:

#2 Ravyne   Crossbones+   -  Reputation: 6460

Like
2Likes
Like

Posted 07 December 2011 - 10:02 PM

Sure. Recursion is at heart a nice way of letting the language manage a stack for you. At minimum you can just create and manage your own stack, though there may be other ways to do the algorithm in an iterative way (eg, recursive functions that accumulate a value).

As to why your scripting language doesn't support recursion, I'd wager that your stack frame mechanism doesn't like it -- but it would do you well to fix it, because it's the more-general case.

What happens when 2 functions are mutually recursive (e.g. When A calls B, which calls A, which calls b, which...)?

#3 compscialien   Members   -  Reputation: 104

Like
2Likes
Like

Posted 07 December 2011 - 10:04 PM

But at the same time, recursion is an important topic in computer programming. So the question is raised: "Why doesn't it return correct values?"

Personally, I'd start by testing the results of non-recursive functions to make sure those are operating correctly under all (or at least most) circumstances. This is where many would preach unit testing as a powerful tool in helping debug applications.

If it isn't a problem with functions in general, then perhaps a deeper analysis of your code would be required. Look at the algorithms that you're using for returning results. Without any information about the implementation, though, I cannot even fathom what could be going wrong there.

Finally, are you sure your function is correct? Is there a possible typo there? That could also easily be an issue.

#4 swiftcoder   Senior Moderators   -  Reputation: 9499

Like
2Likes
Like

Posted 07 December 2011 - 10:23 PM

Technically, yes, any recursive process can be emulated by using an explicit stack (provided your languages has a stack/list/array type, of course). But recursion allows you to much more simply/cleanly specify a certain class of problem, because the compiler can manage the stack for you behind the scenes. Given that your lack of recursion is probably a simple bug in how you handle the stack, I'd say it's well worth fixing...

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#5 Triad_prague   Members   -  Reputation: 136

Like
0Likes
Like

Posted 07 December 2011 - 10:44 PM

YOU GUYS ARE AMAZING!! duh, I'm suddenly going down here....I tried to make 2 functions called each other....it didn't return correct result, just like the recursive function test I did a minute ago. Gwarh I dunno how to fix it. Anyway, what does a real compiler do when a function is called? currently my script function class looks like this:
//this hold the scripted function data (it contains lines of code)
class _s_script_fn_code
{
	int		pad_blocks();		//PLEASE IGNORE THIS...
	int		fix_jump(); 			//PLEASE IGNORE THIS TOO.....
	int		setup_params(std::stack<_s_cvt_token*>& param); //this will copy the parameter to the 'local storage' (function arguments) aka m_args vector...
public:
	_s_script_fn_code();	
	~_s_script_fn_code();   

	int		compile();	//crazy!!
	//execute() IS THE MOST IMPORTANT FUNCTION!!
	//will execute function and operate the stack line (modify it too)
	int		execute(std::stack<_s_cvt_token*>& params, std::vector<_s_cvt_token*>& caller_stack);	//param is a stack of parameters, caller_stack is where the function will return its computation result (it will do caller_stack.push_back(something); )

	std::string			m_name;			//the function name
	int					m_indent;		//IGNORE THIS.........
	std::vector<_s_cvt_token*>	m_args;	//the parameter stack from 'execute' will be copied/referenced to here...
	_s_data_type*		m_ret_type;	//return value type
	std::vector<int>	m_arg_mode;	//parameter modes (PASS_BY_VAL or PASS_BY_REF)
	
	//This contains the compiled code
	std::vector<_s_cvt_line>	m_codes;	//the code (TEH REAL CODE!!!!!!) (this is just a bunch of converted tokens....tokens could be anything (variable, operator, function, constant value)
	//========================================================================================
	//RAW DATA!!! MUST BE CLEARED AFTER COMPILATION!!!
	//THIS IS FOR DEBUGGING PURPOSE ONLY (to show some meaningful texts)
	std::vector<_s_raw_line>	m_raw_codes;	//the raw translated codes (for debugging)
};

I'm lost here. Basically I don't know what a real compiler do when a code call a function. I don't even know how real compiler store/handle functions....Until I know that I won't be able to mimic the same thing to get similar result :(
the hardest part is the beginning...

#6 Cornstalks   Crossbones+   -  Reputation: 6966

Like
2Likes
Like

Posted 07 December 2011 - 11:05 PM

Normal programs use a call stack to make this possible. That is, a function and its local variables get added to the stack, and any functions it calls gets added to the stack... actually, here's a small sample:


void a()
{
    int x;
    x = 2;
}

void b(float y)
{
    std::cout << (y * 2);
    a();
}

void ab()
{
    float theta;
    theta = 3.14f;
    b(theta);
    std::cout << theta;
}

/*
Call stack at beginning: empty

+--------------+
|              | <-stack pointer points to this (empty/non-existent) frame
+--------------+

Now you call ab(), so it gets pushed onto the stack:

+--------------+
| function: ab | <-stack pointer points to this frame
|   -   -   -  |
| theta        | <-space for local variables on the stack
+--------------+

ab() calls b():

+--------------+
| function: ab |
|   -   -   -  |
| theta        |
+--------------+
| function: b  | <-stack pointer points to this frame
|   -   -   -  |
| y            | <-space for parameters (like local variables)
+--------------+

and b() calls a(), so a() gets pushed to the stack and a frame is created for it, just like with the last two:

+--------------+
| function: ab |
|   -   -   -  |
| theta        |
+--------------+
| function: b  |
|   -   -   -  |
| y            |
+--------------+
| function: a  | <-stack pointer points to this frame
|   -   -   -  |
| x            |
+--------------+

Notice how none of them mess with each other's local variables?

Now a() finishes executing and returns, so it gets popped from the stack:

+--------------+
| function: ab |
|   -   -   -  |
| theta        |
+--------------+
| function: b  | <-stack pointer points to this frame
|   -   -   -  |
| y            |
+--------------+
*The frame for a() that was here is longer*

And then b() finishes executing and returns, so it gets popped from the stack:

+--------------+
| function: ab | <-stack pointer points to this frame
|   -   -   -  |
| theta        |
+--------------+
*The frame for b() that was here is longer*
*/

I know this doesn't show return values for the functions, but that doesn't require much work. Once you get the idea of how a call stack works, adding return values is just a matter of making space for it on the stack and filling that space with the right value.

I've also simplified it quite a bit. In real life, there's a few other things that get stored to the stack when you call a function, like your important registers. But again, anything you want to be preserved when you call a function, just make room for it (where the other variables are) on the stack, store them on the stack, and call the other function.

[edit]

Ooohh, just found this.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#7 Vortez   Crossbones+   -  Reputation: 2687

Like
1Likes
Like

Posted 07 December 2011 - 11:09 PM

http://www.unixwiz.net/techtips/win32-callconv-asm.html

#8 Triad_prague   Members   -  Reputation: 136

Like
0Likes
Like

Posted 07 December 2011 - 11:40 PM

Woah thanks for the responses....I think I have to redesign the method in which functions are called!! it surely is flawed, I'll post the result here and I'll ask again when I encounter a problem. Btw ,many many thanks!! :D

EDIT: Duh I'm getting confused so quickly, I don't know how to code it properly now.....and it's full of hack. Do you know any open-source scripting language that support recursion?
the hardest part is the beginning...

#9 rip-off   Moderators   -  Reputation: 7616

Like
0Likes
Like

Posted 08 December 2011 - 05:51 AM

I imagine most popular scripting languages support recursion. I cannot think of any that do not.

How are you currently handling execution?

#10 Antheus   Members   -  Reputation: 2389

Like
2Likes
Like

Posted 08 December 2011 - 10:43 AM

Fun fact: "Goto considered harmful" was advertising move towards structured programming in languages which allow such incredibly high-level concepts as function calls, for loops and recursion. Before then, recursive relations had to be implemented by user since languages didn't support them.


Duh I'm getting confused so quickly, I don't know how to code it properly now.....and it's full of hack. Do you know any open-source scripting language that support recursion?


For stack-based interpreter, things are done quite literally via a stack. Simplest way:
- To call a function, push all parameters (in some specific order, such as left-to-right on stack aka stack.push(param[i])).
- When a function is called, it pops its known parameters off a stack into local variables or temporaries

Example:
// int foo(int a, string b);

// To call
push($PC+3); // program counter, where to continue execution
                   		// assuming each instruction is one byte in length, 
                      	// it continues right after the jmp instruction
push(a)
push(b);
jmp 845; // address/offset of foo function

-------
// the foo function, starting at offset 845
b = pop();
a = pop();
ret = pop();

// do stuff

push(result);
jmp ret;

An incredibly simple approach. Interpreter then trivially converts function calls into sequence of push()es and function body into a sequence of pop()s, connected via jump.

Code converted this way is linear - it has no functions anymore, only absolute addresses. There exist other ways of coding an interpreter, especially if optimization is a concern.

#11 Triad_prague   Members   -  Reputation: 136

Like
1Likes
Like

Posted 08 December 2011 - 08:44 PM

Whoa, thanks for your suggestions!! it supports recursion now, basically for each script function I store:
-information about its local data(local variables and function parameters), how many local vars, how many bytes needed for those local vars.
-its instructions....
-its return type

then when the script calls a function, it will:
-allocate bytes needed for the function's local data + request storage for return value
-point the function to the allocated bytes
-'push' to the call stack (make it the current function)
-execute its instructions

upon returning, it will:
-store any return value it has to store
-release all data it has
-restore call stack or 'pop'

and it worked nicely, I've tested it by making a factorial function inside the script.....now I only need to 'FIX' the stack size (I want to allocate some bytes at the beginning that acts as a stack 'pool', but that's not hard to do)

many many thanks guys !! :lol:
the hardest part is the beginning...




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS