It is currently Sat Sep 22, 2018 10:17 am

 All times are UTC - 7 hours

 Page 1 of 2 [ 23 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Recursion and recursive functionsPosted: Sun Nov 20, 2016 2:02 pm

Joined: Thu Aug 28, 2008 1:17 am
Posts: 591
I'm curious to see; how many of you use recursive methods or functions in your higher level languages, or are comfortable in using it?

I used to hate recursion because I found iteration to be soo more intuitive. But having been forced to use it this semester, I don't dislike it so much anymore. Kind of grown on me.

_________________
__________________________
http://pcedev.wordpress.com

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 2:17 pm

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4076
Watch out for languages that refuse to do tail calls (such as C#), you might get a stack overflow in languages like that. Reassign the function parameters and use a Goto back to the beginning of the function instead.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 2:22 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6817
There are some applications that a recursive function makes simple to write, e.g. flood fill, traversing a tree structure.

You can generally do that stuff without a recursive function, instead just using some kind of stack data structure while the actual code remains in a loop, but the recursive function is often a very succinct way to express these things. It's often a bit of a tradeoff between available stack space and overall efficiency vs. easy/clean code.

There are some languages, like haskell, that don't have loops, and recursion is the typical way to do most iteration.

On the NES, I've so far only wanted a recursive function once, and it was to handle moving blocks that might be stacked on top of each other. (Each block recursively moves blocks that are on top of it.)

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 2:44 pm

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3605
Location: Mountain View, CA
tomaitheous wrote:
I'm curious to see; how many of you use recursive methods or functions in your higher level languages, or are comfortable in using it?

I wrote a recursive function for "string parsing/handling" in a MegaHAL bot I maintain. The PL is Perl. Prior to that, I hadn't had need for use of recursion in over 20 years.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 3:51 pm

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1684
I think that recursive functions are useful when the function simply calls itself with new values, like in a quicksort:
Code:
void Function(int i)
{
// Do something.

if (x)
Function (i - 1);

if (y)
Function (i + 1);
}

But if it's about using the return value in a recursive way, that's where I think a loop would be better:
Code:
int Function(int i)
{
// Do something.

if (x)
return 0;
else
return Function(i + 1);
}

Now that I think about it: Maybe it doesn't have to do with return values, but with the question how often or where the function calls itself again. If it's just once, exactly at the end, then a loop would be better. If it calls itself twice (like in the above example) or if the call happens somewhere in the middle, then recursion is alright.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 4:06 pm

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1013
Usually recursive functions are not needed (except in Haskell) but sometimes it is useful to do.

I have used recursive functions to traverse a tree structure in JavaScript as well as in C and others (and in SQL there is WITH RECURSIVE, which can also be used for tree structures or for other purposes, but it isn't quite the same as a recursive function).

In some cases it is searching a tree structure for something; there are a few different ways to return the result, such as throw/longjmp, or by continuation passing. There is also this way of returning from traversing a tree structure (which comes from a text adventure game which has been automatically compiled into JavaScript; it is used for parsing the player's input):
Code:
const U=x=>x!==undefined;
const PN=(n,t,o,u)=>((U(t.a)&&PV(n,u,o+','+t.a))||(t[WL[n]]&&PN(n+1,t[WL[n]],o,u)));
const PV=(n,t,o)=>(WL.length==n?t.i&&[t.a,t.i,o]:((t[WL[n]]&&PV(n+1,t[WL[n]],o))||(WL[n]<0&&t.n&&PV(n+1,t.n,o+','+WL[n]))||(t.o&&PN(n,NT,o,t.o))));

Another thing is tail calls. JavaScript is supposed to have tail calls but I think V8 (the JavaScript engine used by Node.js) does not currently implement them.

_________________
.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 7:27 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6817
Tail recursion optimization might be important to know about. If you make a self-recursive call at the end of the function, some compilers mayoptimize that call into a loop instead. Example:
Code:
unsigned int function(unsigned int i)
{
if (i < 4)
return i;
else
return function((i+1)/2);
}

Here's the compiled function (MSVC 2013 with /O2):
Code:
if (i < 4)
0121D720  cmp         ecx,4
0121D723  jb          function+0Dh (0121D72Dh)
else
return function((i+1)/2);
0121D725  inc         ecx
0121D726  shr         ecx,1
0121D728  cmp         ecx,4
0121D72B  jae         function+5h (0121D725h)
return i;
0121D72D  mov         eax,ecx
}
0121D72F  ret

Note how what would normally be a recursive call to function has been replaced by an internal loop with jae.

Also, you could do this manually with a goto, and if you really need to rely on it being a loop you should just make it a loop, since optimizations aren't guaranteed in general.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Sun Nov 20, 2016 8:12 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
rainwarrior wrote:
optimizations aren't guaranteed in general.

They are in some languages, such as Scheme. But as you point out, many other languages leave tail call optimization as a quality of implementation issue. A JavaScript implementation is not required to do so, and as of now, only recent Safari does so by default, though V8 (used by Chrome, Opera, and Node) has an "experimental feature" flag to enable it (source). In particular, an implementation may optimize some but not all tail calls, such as Babel (ES6 to ES5 transpiler) that optimizes some tail calls to self (source).

Top

 Post subject: Re: Recursion and recursive functionsPosted: Tue Nov 22, 2016 1:12 am
 Formerly 65024U

Joined: Sat Mar 27, 2010 12:57 pm
Posts: 2263
I was just asking about people's C implementations for when they need this in IRC a couple days ago. My solution was to make a generic C file that has 3 function: Stack_Push(struct list_head *Linux_List,void *), Stack_Pull_(FIFO/FILO), both which return the pointer asked for. It is just a light wrapper around the Linux Kernel's Linked List file. When pushed, it malloc's a node and links it in to the list you tell it to, then when it's pulled it frees it and returns said pointer from the "stack." It worked great for my application. I either had to do that, recurse the function and make it 2x more complex, or use goto's. The goto's would be in odd places, so I used the stack and I think it's the best solution for my use case. Also has the bonus of being able to use many stacks virtually.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Tue Nov 22, 2016 1:54 am

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3605
Location: Mountain View, CA
3gengames wrote:
I was just asking about people's C implementations for when they need this in IRC a couple days ago. My solution was to make a generic C file that has 3 function: Stack_Push(struct list_head *Linux_List,void *), Stack_Pull_(FIFO/FILO), both which return the pointer asked for. It is just a light wrapper around the Linux Kernel's Linked List file. When pushed, it malloc's a node and links it in to the list you tell it to, then when it's pulled it frees it and returns said pointer from the "stack." It worked great for my application. I either had to do that, recurse the function and make it 2x more complex, or use goto's. The goto's would be in odd places, so I used the stack and I think it's the best solution for my use case. Also has the bonus of being able to use many stacks virtually.

If you ever want to look at an alternate implementation (or need one that doesn't fall under the GPL), read the queue(3) man page for FreeBSD (source). These are all macros that handle several different types of lists. There's tree(3) too, for trees (source). These are both used heavily within userland and kernel space. :-)

Top

 Post subject: Re: Recursion and recursive functionsPosted: Tue Nov 22, 2016 1:55 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6817
In C++ if you need a stack data structure, there's a ready made one in the standard template library that works well for a lot of purposes.

If you're limited to C, or STL is otherwise verboten, I wouldn't really recommend using malloc/free for every single stack push/pull operation. Memory allocation from the heap tends to have a lot of collateral (might block threads, synchronize with OS, cause fragmentation, poor cache coherence, etc.). If you do need to keep your stack structure dynamically allocated on the heap, instead of allocating every single node of a linked list you might consider a chunky variation of the linked list to reduce the number of allocations needed?

Every malloc has to store some extra bytes to keep track of the allocation itself, plus the linked list wrapper structure, plus whatever you were putting in the stack in the first place. You could easily be inflating the memory cost of your stack by 100x by allocating every single push separately.

If you want a fast stack, you probably can't beat just using an array (allocated once you know the maximum size needed, possibly at compile time). A std::stack should typically be almost as good as a static array. Even an efficient linked list will be significantly slower. A recursive function is probably in between, due to the extra overhead of function calls, but has the disadvantage of a very fixed size (dependent on the environment).

Top

 Post subject: Re: Recursion and recursive functionsPosted: Tue Nov 22, 2016 2:06 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6817
koitsu wrote:
If you ever want to look at an alternate implementation...

I think it's worth implementing basic data structure algorithms for yourself at least once or twice to learn how they work.

Once you've done that, though, take a look at some well-used implementations and get to know them. Sometimes it's appropriate to write a new one, but most of the time there's actually something out there that's a good fit that will save you a lot of time.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Tue Nov 22, 2016 6:31 pm

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1013
In C programming I do normally just use an array for a stack; there is also a way to keep track separately of allocated stack size and in-use stack size and to use realloc if you need to add more than the allocated size. (However, sometimes there are variable size; in such case it may be simpler to use malloc especially for large data on one stack item.)

In JavaScript there is built-in Array.prototype.push and Array.prototype.pop functions for implementing a stack.

In Haskell it is also easy due to how lists work; it is like a cons-cell and you can easily do pattern matching with it. (Although, in many cases especially in Haskell recursion is probably more helpful.)
Code:
push x = state \$ \y -> ((), x:y);
pop = state \$ \(h:t) -> (h, t);
popm = state \$ maybe (Nothing, []) (first Just) . uncons;

And then in Forth, there is stack built-in.

Z-machine also has one data stack local to a function call; YZIP has instructions to deal with additional stacks stored in addressable memory.

Another thing that uses recursion is if you are writing a recursive descent parser.

But in many cases recursion can help better especially if you do not need to be too deep.

rainwarrior wrote:
Tail recursion optimization might be important to know about. If you make a self-recursive call at the end of the function, some compilers mayoptimize that call into a loop instead. ....Here's the compiled function (MSVC 2013 with /O2):....
Other C compilers are GCC and clang and it can help to know how well it work with those too.

Quote:
Also, you could do this manually with a goto, and if you really need to rely on it being a loop you should just make it a loop, since optimizations aren't guaranteed in general.
In a lot of cases that does help (but not tree structures), and does make more sense. (Some programming languages don't have goto, but usually a loop will do anyways.)

_________________
.

Last edited by zzo38 on Wed Nov 23, 2016 2:54 pm, edited 1 time in total.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Wed Nov 23, 2016 12:16 am

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7518
Location: Chexbres, VD, Switzerland
Personally I'd just use what comes to me naturally. One example where I had to use recursion is to parse mathematical expressions in CompressTools. I'd detect the position of parenthesis in the string, and if there is any pair of parenthesis I'd just have the parse function call itself with the substring that is between the parenthesis. It just make sense. If I had to do it without any recursion, I'd be in big trouble to have a loop that does the equivalent.

However, I'd admit that most of the time I do not use any recursivity in my algorithm because it's largely unneeded. I believe it can look butiful in some high level code such as Haskell, but when coding in low level language it is just a waste of memory for something that can be done more efficiency without.

I'd also warn about some example of recursion, some are actually algorithmically slower than doing it with a loop. The typical example is the fibbonaci. You can define fibbonaci as :

fibbonaci (n) = fibbonaci (n-1) + fibbonaci (n-2)

However if you actually implement it that way in a computer, it will be awfully slow to computer, say, fibbonaci(24). But doing it with a loop is blazing fast. That's because each call to fibbonaci leads to 2 more calls, and that 24 times, so we need 2^24 calls (if I am not mistaken !), while using a loop you just do 24 iterations of the loop and basta.

Top

 Post subject: Re: Recursion and recursive functionsPosted: Wed Nov 23, 2016 9:16 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
You're right that recursion other than tail recursion can prove very time- and space-inefficient. One workaround is "memoizing", or caching previously calculated values. Another is to convert it to a tail recursion by passing the next iteration's state as arguments:
Code:
def fibonacci(n):
"""Calculate the nth Fibonacci number"""

def inner(n, cur, prev):
"""Run the Fibonacci computation for n more steps"""
if n <= 0:
return cur
return inner(n-1, cur + prev, cur)

return inner(n, 1, 0)

(Full disclosure: Python doesn't optimize tail calls because its debugging model doesn't allow it. Source: part 1; part 2)

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 23 posts ] Go to page 1, 2  Next

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki