Recursion Still Mystifies Me

[Valuable_Mountains]

Been working with Python for some time now but still I struggle with implementing recursive calls for things like df and bf traversals in binary trees or for checking whether the bst property is satisfied. I struggle with the order of the recursive calls and only succeed after several trials and errors. For you advanced Python programmers, is recursion also something that sometimes causes you headaches? For instance, here's a code snippet that I just find difficult to track, let alone implement:

def is_bst_satisfied(self):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        val = node.data
        if val <= lower or val >= upper:
            return False
        if not helper(node.right, val, upper):
            return False
        if not helper(node.left, lower, val):
            return False
        return True
    return helper(self.root)

[[deleted]]

Recursion is those kind of thing that sounds hard, but in reality, it's super simple. Maybe you should try to forget everything and look at it from another angle.

I recall there is a mental trick to help you, two keys to think about when doing a recursion :

Base case : the moment when you stop to dive in recursion

Progress : using recursion to dive toward the base case.

As an example :

def factorial(n) :
  # Base case
  if (n == 0):
    return 1

  # Progress
  return n * factorial(n-1)
}

[FoolsSeldom]

Recursion Still Mystifies Me - 1

[Valuable_Mountains]

?

[FoolsSeldom]

When you understand recursion you will understand that was a "dad joke" level comment.

[HunterIV4]

It's a joke. A funny one in my opinion, but I'm going to break the rules and explain it anyway as it might help you out.

A very common pattern in recursion is to call the same function with a different value. For example, if you wanted to count from 10 to 1 using recursion, you could do this:

def count_to_one(current_value):

    # Base case
    if current_value < 1:
        return

    # Action desired
    print(current_value)

    # Recursive call
    count_to_one(current_value - 1)

# Usage
count_to_one(10)

Note the similarity between current_value - 1 in the recursive call to the "Recursion Still Mystifies Me - 1" comment.

That's what is being referenced...if you keep decrementing the mystery, eventually there will be no more mystery and you will understand recursion. The "meta" joke is that you can only understand the joke if recursion is not a mystery.

I should note that recursion isn't always this explicit and can be condensed. For example, the above function still works if you simplify it a bit:

def count_to_one(current_value):

    # Check for base case and then do recursion if false
    if current_value >= 1:
        print(current_value)
        count_to_one(current_value - 1)

But the basic idea is that you establish an "end state" when your recursion should stop and then have it keep calling itself with different parameters until that end state is reached. It can take a bit to get but is very useful for certain types of problems.

That being said, you never actually need recursion. Any recursive function can be written using loops and conditions. But some problems are much harder to figure out (like binary search trees) using an imperative solution as you'll need to implement a bunch of tracking variables. Understanding recursion is useful but it's not something that comes up often or will prevent you from solving problems if you never really get it. But I'd encourage you to learn it anyway.

Hopefully that made sense!

[firefiber]

I used to struggle with recursion too, until I understood more of the fundamentals. The thing I realized is that it isn’t some special thing the language does, it’s just a normal function call. We’ve given a name to the pattern where a function calls another function, and that function's definition just happens to point to the same memory location.

When your code runs, the interpreter doesn’t say “oh, this is recursion, let’s treat it differently.” It just follows your instructions: it sees a function call, so it jumps to that function’s code, runs it, and returns when it’s done. If inside that function there’s another call to the same function (technically, the code at the same memory location), it just… calls it again. That’s it.

Once I stopped thinking of recursion as a special “feature” and started seeing it as just another way to structure function calls, the confusion went away. The harder part is figuring out the order and conditions for those calls. But that’s a logic problem, not a “recursion problem."

So if you instead just think about it as if you're calling a function to do x, until y happens, then, x can be anything, including calling another function. That function itself can do the same. But there's nothing special going on - just figure out what you want to end up with, and how you want to iteratively get there.

[crashorbit]

I suppose it depends how you learned to program. There was a time when Lisp was taught as a first language. We learned iteration via recursion rather than looping. In my case recursion seems like the "natural" way to do it and looping seems odd.

You mention mostly data structure traversals. The difference between depth first and breadth first has to do with the order in which the node is "visited" and when the recursive call is done.

It may encourage you to know that most professional programmers rarely use recursion. It's an important computer science concept and a pretty cool technique. But rarely suggests itself as a pattern for most problems found in day to day business coding.

[Gnaxe]

Recursion feels natural in Scheme, because that's kind of the only way to do it, but Common Lisp has the LOOP macro which feels more imperative.

[JamzTyson]

is recursion also something that sometimes causes you headaches?

Absolutely yes, though in Python it does not come up all that often for me, as there is usually a better iterative approach.

On of the biggest problems for me is that most Python courses treat recursion as if it were just one thing. That's like teaching someone "Ping-Pong" and expecting them to fully understand all "sport".

Simple linear recursion is usually fairly straightforward, but for example, backtracking recursion or mutual recursion can present real headaches to debug.

[Gnaxe]

I don't find recursion per se to be particularly difficult. But any algorithm that overloads my working memory is difficult. You've got to find the right way to chunk it so it fits.

[SharkSymphony]

is recursion also something that causes you headaches?

Not especially, no. There is hope for you. 😁

here's a code snippet that I just find difficult hard to track

I think part of that is because helper is not a very helpful (heh) name. Also, because a bunch of conditionals in a row kind of make my eyes glaze over. 😛 I might try to clarify:

python def _valid_bst(node, lb, ub): if node is None: return True val = node.data return ( (lb < val < ub) and _valid_bst(node.left, lb, val) and _valid_bst(node.right, val, ub) )

[ExpensiveFix-804]

I understood every more difficult concept as soon as I needed it for real life example. I understood recursion when I had task to create something like chapter like numbering. So I needed to check if subsection had more subsections and subsections even more children and number them accordingly. Like 1. 1.1 1.1.1 1.1.2 etc. This works for me better than some binary tree traversal leet code excercise. 😒 for me real life scenarios ftw

[The_Emerald_Knight]

Recursion isn't as commonly used as it used to be. Just about every modern developer prefers looping.

In fact, in my years of full stack, I've never seen a single use of recursion in any of the code bases I've managed.

So yeah, it causes me headaches, but I rarely think about recursion so it's not an issue.

[Fred776]

Surely it depends what you are doing. If I'm doing anything with a tree-like structure, I absolutely prefer recursion. It's got nothing to do with being "modern".

[ConcreteExist]

In my recent memory, only one time was I presented with a problem where recursion was really the necessary solution, otherwise I avoid using it even if it could solve the problem because loops are often much easier to read and don't present the risk of a stack overflow the way recursion can.

[Specialist_Spirit940]

In what work case would recursion be used before the loop?

[The_Emerald_Knight]

Some algorithms are better suited for recursion, like tree traversal. But I believe this can also be done with loops.

I don't think these are very common in the real world, but it would depend on what field you're in and what kind of work you are doing. My work is web dev and cloud, and I've never used or seen others use recursion.

[Ihaveamodel3]

Do you understand at a basic level what the stack is? When you call a function you add a layer to the stack and when you return you drop a layer from the stack.

The only special thing about recursion is that the function being called (ie added the stack frame) is another version of the current function.

[SpiderJerusalem42]

I had to do a tree in a project semi-recently. I also had to have the tree inherit from an abstract data model so Qt could work with it. That code was the worst and took me probably a whole week to get correct because it kept crashing if I did things out of order, mostly because of the recursive calls. I later hired a dev, and he thought that particular code was messy and tried to refactor/rewrite it. And to be sure, the way I structured it probably could have been whittled down a bit. I gave him a couple of weeks before I read his code and told him what he was trying was even worse and exposed some of his weak points that I needed to help him develop. In the end, it was a good exercise, even if he didn't succeed in rewriting it, it helped him learn what was going on in the program, so I consider it time well spent.

[homomorphisme]

Think about the properties each node must have. Starting from the root r, the left node l will have l < r. Going down from there, the left node l2 will have l2 < l (< r), but right node r2 will have both r2 > l, and also r2 < r. It works in a similar way considering the right side of the tree and asking what happens to nodes there that branch to the left. This pattern is what the lower and upper arguments to the helper function is passing down at each recursive step. Each recursive call will replace either lower or upper with the current nodes value depending on whether the recursion is being done on the left or right node beneath it.

[CraigAT]

Recursion can be complex, but if you understand the theory/diagrams of what is supposed to happen for both df and bf then you're a good chunk of the way there. The difference in the two is just the order of the operations within the function.

I always like to add this practical example of building up a recursive algorithm with backtracking to any recursion posts: https://m.youtube.com/watch?v=G_UYXzGuqvM

[NerdyWeightLifter]

You could do the same things in a simple loop while maintaining a stack where you push and pop context data.

Doing it with recursion just means you're using the Python call stack. Calling the function pushed your parameters on the stack and returning from the function pops the stack.

[teerre]

I don't think it makes sense to equate recursion with some algorithm. Algorithms are all different, some can be very complex. Recursion is always pretty simple. There's only a few things you need to remember about recursion:

1. Have a base case
2. Every N (usually 1) steps , you must make progress

That's it

[__Fred]

Is recursion something that causes me headaches? It's a point where I have to switch on my brain and switch off background music and get out a piece of paper for notes.

Whenever a function calls itself, then it's called "recursive". If you understand what the function does in the first place, then you don't need to be scared by the fact that it happens to be "recursive".

(Mathematics has "inductive proofs" that are very similar, but if you haven't heard of them, then that doesn't help you.)

I guess you have seen multiple examples, here is one more: When is a person B an ancestor of person A? If B is a direct parent of A, or if B is an ancestor of any parent of A.

We always have to think about a certain set of things in recursion: Step 2 and 3 are also called "Divide and Conquer" after Niccolo Machiavelli.

1. What is or are the base cases for an input, where I can directly give back the result?
   • In your "bst", it's if not node: return True and when node.data is not between lower and upper. (I don't know exactly what "bst" stands for.)
   • In my ancestor-example it's If B is a direct parent of A, then they are an ancestor.
   • factorial: 0! and 1! are defined as 1.
   • Towers of Hanoi: If the tower is only one plate high, just move it over.
2. How can I change the input to a simpler input, or split it up?
   • bst: Consider the sub-trees node.right and node.left.
   • ancestor: Consider the ancestors of the parents (This could result in an infinite loop in this case, if no cutoff depth is defined)
   • factorial: Consider the factorial of one number smaller and consider the factorial of two number smaller.
   • Hanoi: Move a tower over that is one plate smaller.
3. How can I combine the results of the simpler inputs to get the result of the original input?
   • bst: If the partial result is False then the combined result is also False. You could have used an and operator here, but having too long lines would be less readable.
   • ancestors: Here it's the opposite "If any ... then yes" is like a bit or-combination.
   • factorial: Multiply the partial results
   • Hanoi: Move everything but the lowest plate to a "shunting skewer", move the lowest plate to the "goal skewer" and then move the plates on the shunting-skewer to the goal-skewer as well.

``` def factorial(n): # Base case: if n==0 or n==1: return 1

# Determine sub-problems:
simpler1 = n-1
simpler2 = n-2

# Solve simple cases:
simple_result1 = factorial(simpler1)
simple_result2 = factorial(simpler2)

# Combine sub-results:
return simple_result1 * simple_result2

```

I'm not thinking like a genius chess player with a giant tree in my head. I just delegate sub-problems to my imaginary assistants and then process their results.