• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Triad_prague

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

10 posts in this topic

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
0

Share this post


Link to post
Share on other sites
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...)?
2

Share this post


Link to post
Share on other sites
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.
2

Share this post


Link to post
Share on other sites
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...
2

Share this post


Link to post
Share on other sites
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:
[code]
//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)
};
[/code]

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 :(
0

Share this post


Link to post
Share on other sites
Normal programs use a [url="http://en.wikipedia.org/wiki/Call_stack"]call stack[/url] 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:

[code]

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*
*/
[/code]

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 [url="http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/stack.html"]this[/url].
2

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
I imagine most popular scripting languages support recursion. I cannot think of any that do not.

How are you currently handling execution?
0

Share this post


Link to post
Share on other sites
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.


[quote]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?[/quote]

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:[code]// 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;
[/code]

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

Share this post


Link to post
Share on other sites
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:
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0