Illustrating: Recursive Functions

Question

Sometimes when we learn about a tool, the first thing that comes to our mind is "and why would I ever use that? that's totally useless". But later we find out it is extremely useful - when used right. And we learn that by looking at good examples. So I'd like to see nice examples of some common tools, starting with Recursive Functions. A recursive function, of course, is a function that calls itself. The classic example is a factorial function.

This is not a challenge, but can be thought of as one. Whatever function you come up with, make sure that it works well by being recursive (depending on what it does, it can be a terrible idea). If possible, add an explanation to it.

All languages welcome.

Answer 1

Here's an interesting one: The ackermann function.

function A(m, n){
if(m==0) return n+1;
if(n==0) return A(m-1, 1);
return A(m-1, A(m, n-1));
}

It was designed to grow super quickly - wikipedia says A(4,2) has ~20 000 digits - but it always stops and won't get stuck in a loop. It belongs to a nasty breed of recursive function (non-primitive recursive) that can't be represented well without recursion.

Answer 2

i make mine recursive functions everytime for a challenge , some programs are very hard without recursion [U'll find some on google , google some challenges on codeforces.com & get started ... ohhh yeahhh!!! ,very interesting & fun challenges]
//have look at this , might be hard without recursion
//don't forget 2 see my other codes also
https://code.sololearn.com/cShYxjjWyC8R/?ref=app

Answer 3

Usually I avoid recursion..
You don't have a good control over the flow of your program.

This time I found it useful.. but keeping in mind it's called just few times!

https://code.sololearn.com/cQeWjNa05nS8/?ref=app

Answer 4

As Ace stated, recursion has a cost that might be prohibitive compared to using loops. Here are a couple Java examples:
https://code.sololearn.com/cZ2SIVlkZ4a4
https://code.sololearn.com/cx85EY10cNk7

Answer 5

Mine is the following...

With python:
https://code.sololearn.com/c6Pu0S63vOII/#py

It's a custom_len() function. If the argument given to it is a list of strings, it returns a list with the length of each string (instead of returning the length of the list itself, as len() would do). So do so, it calls itself on each term. (Works for a list of lists as well.)

Answer 6

@Ace

That's not what I meant, but I did indeed choose bad words. Edited. Thanks.

Answer 7

I figured I'd play with Ackermann in Kotlin:
https://code.sololearn.com/cGXMcw3XP6yW

Answer 8

Schindlabua comment about Ackermann made me want to try it. Plus, there is another discussion about looping vs recursion, where I stated anything done in either can be done in both so I had to prove it. This contains both my recursive program above plus a looping version. Those who wish to see the other discussion can find a link in my program comments.
https://code.sololearn.com/cjOi8G54yytD

Answer 9

First one that came to my mind was The Ackerman Function since I remember running & analyzing it in one of my comp Sci classes. The professor let us leave the lab computers running overnight since it would take so long to run; We were analysing recursion runtime. So, pretend I wrote exactly what Schindlabua did since he beat me to it. *high-five*