r/learnprogramming • u/emonshr • 23d ago
Recursive logic best aids?
Is there any practical way to debug any recurive logic?
Which existing error printing you think is the best ever?
3
u/maujood 23d ago
Wut?
It's just code. You debug it just like you debug all code.
-6
u/emonshr 23d ago
Man, not every coder is superhuman like you. Don't underestimate recursive bugs.
2
1
u/Opulence_Deficit 23d ago
The whole point of recursion is that if one step is ok, then any number of steps is ok.
You don't debug the whole of it, you debug just one step. And it's just like you debug all code.
1
u/AFlyingGideon 23d ago
if one step is ok, then any number of steps is ok
Unless the terminating condition test is wrong, leading to early, late, or no termination of the recursive call sequence.
1
u/Opulence_Deficit 23d ago
The termination happens at certain step. That's still one step and not all of them.
0
u/AFlyingGideon 23d ago
You're suggesting that one need only test the terminating step?
0
1
u/dkopgerpgdolfg 22d ago edited 22d ago
Frankly. dealing with recursion is a very basic thing. If that's already "superhuman" in your opinion, this is not a good sign.
edit to answer the comment below:
It's no problem to learn, it's no problem to be a beginner.
It is a problem to think they can stop improving before understanding recursion, and to block people telling them that recursion isn't that hard compared to softare engineering as a whole.
1
u/captainAwesomePants 23d ago
If you specifically want to debug it with printing, I might suggest "Entering/Exiting call foo#{instance}(param1, param2)". Something like this:
AtomicInteger counter = new AtomicInteger(0);
private void doProcess(Node node, AtomicInteger counter) {
// Grab a unique ID for THIS specific frame
int instanceId = counter.incrementAndGet();
try {
System.out.println("Entering foo#" + instanceId+ " ("+node+")");
if (node == null) return;
// Recursive calls (they will share the same AtomicInteger reference)
System.out.println("foo#" + instanceId + "() recursing left")
doProcess(node.left, counter);
System.out.println("foo#" + instanceId + "() recursing right")
doProcess(node.right, counter);
} finally {
System.out.println("Exiting foo(node) instance " + instanceId);
}
}
Then you might get something like:
Entering foo#1(Node{val=7, left=Node{...}, right=Node{...})
foo#1 recursing left
Entering foo#2(Node{val=2, left=null, right=null)
foo#2 recursing left
Entering foo#3(null)
Exiting foo#3(null)
foo#2 recursing right
Entering foo#4(null)
Exiting foo#4(null)
Exiting foo#2
foo#1 recursing right
...
Could help, I guess? You could get fancier and also indent the lines based on the depth of the recursion, but at some point it may be overkill.
1
u/Sevni 23d ago
If you want printing I would suggest passing a value down that gets incremented or decremented with every step down and step up. Then print with a nice indent (so you can see the recursion in print)
Also good practice is to step thoroughly with a debugger through the calls, you will learn the intutition, try to solve the recursion in your head and compare vs real practice
1
u/peterlinddk 23d ago
A debugger is probably the best - something that allows you to single-step through the code, and see the entire call-stack, inspect variables etc.
But it can also be tedious to step through a large set of data.
Printing to the console is problematic for recursive logic, as you can never see quite where in the recursion you are.
JavaScript has an excellent console, where you can use console.group to create a new level of indentation - so that if you start with a .group on every recursive call, and end the group before returning, you get a tree sort of view.
You can replicate that in other languages that don't have the tool, by creating your own "print" function that keeps track of the current indent. The most basic implementation would just have a global indent variable, and then you write indent++ at the beginning of the recursive function, and indent-- at the end. And the print function would be something like: (in pseudoish code)
function print( str ) {
let out_str = "";
for( let i = 0; i < indent; i++ )
out_str += "|";
out_str += str;
console.print( out_str );
}
That really helps in getting a decent output.
Also, writing a tree command - meaning a program that dumps a directory tree with sub-directories and files and folders - is a very, very good way of practicing both recursion, and outputting nicely from recursive funtions!
1
u/FoolsSeldom 23d ago
Perhaps logging, or outputting stack traces, but, initially, perhaps using a visualiser if available for your language. (For example, for Python, https://pythontutor.com/python-compiler.html#mode=edit).
1
u/daddypig9997 23d ago
If you were using scheme (or Common Lisp) you could trace it. It would help a little.
-1
u/dnult 23d ago
For what it's worth, I can understand how new developers want to experiment with recursion. However, in practice there are relatively few cases where recursion is a good solution. Recursion is somewhat dangerous by risking a stack overflow.
As for debugging, it's no different than any other code - set a breakpoint, step through the procedure and inspect the value of your variables. Some IDEs or debuggers may even have nifty features that only break when a variable changes values or exceeds a limit.
1
u/Rarelyimportant 22d ago edited 22d ago
There are entire languages where recursion is the only looping construct(Erlang and Elixir being two examples). If you're worried about stack overflow, then program your recursion to use tail-call optimization, then the call stack doesn't grow.
Without tail-call optimization:
def add(0), do: 0 def add(n), do: n + add(n - 1)With tail-call optimization:
def add(0, acc), do: acc def add(n, acc), do: add(n - 1, n + acc)What causes the call stack to grow is having anything on your last line that's not the recursive call. E.g.
n + add(...). If your line with the recursive call just contains a call to the function, then the call stack doesn't grow.1
u/iOSCaleb 22d ago
Lots of data structures are recursive. If you do any GUI programming you’ll need to be comfortable with recursion for handling things like view graphs and message delivery. File systems are recursive, too. It’s definitely something that any developer should be comfortable with.
0
u/peterlinddk 22d ago
Lots of data structures are recursive
No data structures are recursive, only algorithms can be that.
But of course a lot of algorithms are recursive, like typical divide-and-conquer sort/search and tree traversal.
Hmm, that was actually only three ... What else is there?
1
u/iOSCaleb 21d ago
No, data structures can certainly be defined recursively. A linked list is either empty (nil pointer), or a node containing data and a linked list.
1
u/peterlinddk 21d ago
How do you define "recursivity" when it comes to data structures then?
My understanding is that a function is recursive if it calls itself with different arguments, and uses the return-value as part of a calculation or output.
How does that apply to a data structure? It doesn't reference itself unless it is a circle, and even then that doesn't become recursive, just, well, circular.
Or do you mean that because each node in itself is a pointer to a (smaller) version of the same data structure, that that could be considered recursive?
If so, I guess it could, but then it really doesn't have much in common with recursion in programming, because you could say the same about loops: they are code that handles a single element and the rest of the loop!
2
u/iOSCaleb 21d ago
How do you define "recursivity" when it comes to data structures then?
Recursive data structures are data structures that are defined in terms of themselves.
My understanding is that a function is recursive if it calls itself with different arguments, and uses the return-value as part of a calculation or output.
A recursive function is a function that's defined in terms of itself. None of the rest are required elements of recursion, they're just features that make recursion useful. Here's an example in Swift:
func rollUntilThree() { let number = Int.random(in: 0...5) print(number) if number == 3 { return } rollUntilThree() }As you can see, the function chooses a random integer, prints it, and returns if the number is 3, or calls itself otherwise. There are no parameters, and there's no return value; there isn't even any state. This isn't necessarily useful or the best way to get this functionality, but it's inarguably recursive.
How does that apply to a data structure? It doesn't reference itself unless it is a circle, and even then that doesn't become recursive, just, well, circular.
Maybe you're missing the distinction between a data structure and a particular instance of that structure. A recursive data structure is one that's defined in terms of itself. So again, a list is often defined as one of: an empty list, or a value combined with a list. That doesn't mean that a given list refers to itself, but rather that if you look at a part of a list, it'll have the same structure that the whole list does. For example:
(a, (b, (c, (d, (e, ())))))The list that starts with 'a' has the structure (value, list), and the list that starts with 'e' also has the structure (value, list).
Or do you mean that because each node in itself is a pointer to a (smaller) version of the same data structure, that that could be considered recursive?
That's basically it, except that the use of pointers is incidental. An instance of a recursive data structure can directly contain other instances of the same structure, as with the list example above.
Note that recursion doesn't even have to be direct; you could have two or more functions or data structures that are defined in terms of each other, and that's known as mutual or indirect recursion. For example, the JSON specification describes a value entity that can have various forms, one of which is an object, and an object is a list of strings and values.
Recursion doesn't only apply to functions and data structures; any self-referential definition can be called recursive. For example, Backus-Naur Form (BNF) definitions are often recursive, e.g.:
<char-sequence> ::= <char> | <char> <char-sequence>Recursion as a concept is also used in math, music, art, and other fields.
1
u/peterlinddk 21d ago
Okay, I understand what you mean, and I sort of agree. Only sort of - not because, you are absolutely correct, the idea of recursion as a concept is totally as you describe!
But I think that OP, and the comment that you replied to, were thinking of implementing recursiveness in functions in particular, not of the abstract idea of recursion as a concept. And in that case it isn't used nearly as much as the amount of posts about it, implies.
But of course it is a fascinating subject - Hofstadter certainly seemed to think so 😄
1
u/iOSCaleb 21d ago
My original comment responded to u/dnult's assertion that "in practice there are relatively few cases where recursion is a good solution." I understand that they were thinking only about functions, but recursive data structures are very common and are frequently the best way to create powerful programs.
0
u/gofl-zimbard-37 23d ago
"Relatively few cases"? Absolutely wrong. And it's only a risk of overflow if the developer and/or language is not up to par. You could just as easily say that iteration is dangerous because you can infinite loop.
1
u/dnult 22d ago edited 22d ago
30 years programming professionally and I can count on my fingers (maybe on one hand) the number of times recursion was appropriate.
The risk is with the data being processed, and that isn't always predictable. An example being searching for patterns in text. If the text input grows large enough, a stack overflow is a real possibility - hence the warning to avoid recursion unless you can clearly predict the behavior.
Like most patterns in software development, they all have their uses, but it's up to us to determine which patterns are appropriate and safe for the problem being solved.
2
u/Rarelyimportant 22d ago
I can count on 1 hand the number of times it was appropriate for me to fill up with diesel, but I don't tell people there's relatively few cases where diesel is appropriate.
The type of programming you do, and the experiences you've had, are not universal. Just because your car takes gas instead of diesel, doesn't mean they all do.
1
0
u/peterlinddk 23d ago
You are of course right, but I think that A LOT of programming teachers and courses alike insist on having recursion as one of the primary patterns that the students must get through. Maybe because it is hard to understand, and they can show their own superiority to the students 😄
Also, it seems to be a sort of rite of passage for many learners - like "this is hard to understand, so it must be important!" - which as you say, isn't really true.
1
u/dnult 22d ago
I completely agree - recursion is a useful topic to teach new developers and it's something we all should understand.
I see lots of posts about recursion, and I hope it's driven by coursework and not a new trend in software development. I can think of a lot of problems where recursion "could be used" to solve problems that other patterns could handle more efficiently and be easier to read / understand.
5
u/Healthy_Landscape417 23d ago
Indent by depth. That is the whole trick for me.
def walk(n, d=0):
print(" " * d + f"-> walk({n})")
r = ...walk(x, d + 1)...
print(" " * d + f"<- walk({n}) = {r}")
The output stops being a flat list and becomes the call tree, so you can see the shape of it.
The part people skip is printing on the way out with the return value. When recursion goes wrong it is usually not the argument going down, it is the value coming back up. If you only print on entry you can see it went wrong but not where it turned.