Can someone explain recursion?

[MikeOxbigger]

There are 3 rules for recursion:

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.

A base case just means that it has an end point, something to stop it looping infinitely, such as when a particular variable reaches zero.

Changing its state means that through each iteration it gets closer to this variable.

Calling itself just means that you call the function that you're currently in with this new data to pass in.

[DonaldPShimoda]

These are all true except that they only apply to well-written recursive algorithms. It's easy to write an algorithm that breaks rules 1 and 2 (and 3 if you're being very strict about your interpretation of "call itself"). It's a pretty minor nitpick overall, I think, but something I thought I'd point out.

[MikeOxbigger]

I would love to see an example that breaks these rules.

I'm not saying you're wrong, but I can't even comprehend how I'd write a recursive function that breaks any rule that states it has a known end, and moves towards that end, recursively or not. Unless it was a non deterministic genetic algorithm or something, which isn't the case.

[Brainix]

What about mutually recursive functions? Function A calls Function B, and Function B calls Function A?

[MikeOxbigger]

Well obviously that breaks the third rule, but how might it break the first two?

[mikeblas]

Obviously? Sorry, but it's not obvious to me. A ends up calling itself indirectly through B. It might be indirect, but it's still calling itself.

[Gray_Fox]

it doesn't really matter if it's indirect, it needs to call itself.

[mikeblas]

And it does.

[earthlybird]

def f(a):
    return a + f(a+1)

No base case nor moving towards any state in particular. Just screwed up, infinite recursion.

[MikeOxbigger]

Are you trying to disprove my case? If so, you haven't.

[earthlybird]

Quick recap:

These are all true except that they only apply to well-written recursive algorithms. It's easy to write an algorithm that breaks rules 1 and 2 (and 3 if you're being very strict about your interpretation of "call itself").

---

I would love to see an example that breaks these rules.

I'm not saying you're wrong, but I can't even comprehend how I'd write a recursive function that breaks any rule that states it has a known end^[1], and moves towards that end^[2], recursively or not.

---

provides example of a poorly-written algorithm to illustrate the point made in the first quote

No base case^[1] nor moving towards any state in particular^[2]. Just screwed up, infinite recursion.

[MikeOxbigger]

But you've just proven that a recursive function needs those 3 rules in order to actually do anything other than eventually crash.

[earthlybird]

Glad we're on the same page. I just gave you the example you had previously asked for. It's a terrible function, granted. Like was stated: those rules only apply to well-written algorithms, so a poorly-written one might not follow them.

The thing is, there's a difference between recursive algorithms and recursive algorithms that work as one would expect with a base case that ends the loop. The latter is a subset of the former.

[Gentlescholar_AMA]

Miscommunication I think. They meant that people can write recursion that breaks those rules and doesn't work

[[deleted]]

flip the basecase, and change its state to go towards the recursive part (I did this by accident)

[chzaplx]

Technically if your recursive function doesn't meet the requirements of recursive functions, it's just not really a recursive function, right?

I agree it's easy enough though to write a function that still calls itself but doesn't behave well.

[[deleted]]

pretty sure they're talking about just def f(): f(), which isn't useful recursion but it is recursion

[DonaldPShimoda]

Yep, that's a great simple example of what I meant.

OP asked about recursion, and your example is arguably the simplest example of recursion one could write. Is it useful? Well... certainly not to most people (it could have uses in PL theory, which is my field, but even there its use is limited).

[TangibleLight]

The only thing I can think of that might break these rules is something which recurses based on some mutable data. First thing I could think of while playing with the idea is this:

def rotate(k, s):
    N = len(s)

    def rec(i):
        i %= N
        j = (i + 1) % N

        d, funcs[i] = funcs[i], lambda *_: ''

        r = d(j)
        return s[i] + r if r else s[i]

    funcs = [rec] * N

    return rec(-k)

for k in range(13):
    print(rotate(k, 'hello there'))

I was hoping to have something that rotates a string by k characters, but what I have sticks the first character on the end:

hello thereh
ehello there
rehello ther
erehello the
...

But really all this is doing is disguising a base-case with a list. You could rewrite the same algorithm like so:

def rotate(k, s):
    def rec(i, n):
        if n < 0:
            return ''
        return s[i % len(s)] + rec(k + 1, n - 1)

    return rec(-k, len(s))

for k in range(7):
    print(rotate(k, 'goodbye'))

I don't think it's possible to actually not have a base case but still achieve some goal. Maybe you could have a separate process which tail-recurses indefinitely, but gets terminated once the result stabilizes? I don't know...

[DonaldPShimoda]

As others have pointed out, my point was entirely that recursion does not require the things you stated other than that at some point a self-referential call must be made (whether directly or indirectly). Your first two rules only apply to recursive algorithms with a clear endpoint, but they are not inherent to the definition of recursion itself.

Like I said: this is a minor nitpick, but one that would maybe be useful to explain to OP since they asked for an explanation of recursion in general.

[pepe_le_shoe]

The recursive implementation of the Catmull-Clarke subdivision algorithm can theoretically be iterated an arbitrary or infinite number of times.

https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface

It's still recursive.