-
Hey,
I am trying to implement bubble sort using recursion and have got a response
ArrayIndexOutOfBoundsException: 11
Unable to figure out where I went wrong..
public static int[] recBubSort(int []arr, int n){
if(n > arr.length-1){
return arr;
}
if(arr[n] > arr[n+1]){
swap(arr,n,n+1);
}
return recBubSort(arr,n+1);
}
public static void swap(int arr[], int minPos, int index) {
//System.out.println("SelectionSort SWAP...");
int temp = arr[minPos];
arr[minPos] = arr[index];
arr[index] = temp;
}
-
If arr is [0,1] then arr.length = 2
If n is 1 then n is not greater than arr.length - 1 and following condition attempts to access arr[n+1].
So the bounds check condition is wrong, and should be if (n >= arr.length - 1).
-
First thing we can notice is that you check for n: 'if(n > arr.length-1)' as your exit condition.
Problem is: "n == arr.length-1" is thus a valid case for what follows. You then access arr[n+1], which in this case would be arr[arr.length], which will be out of bounds because array indexing starts at 0.
So you need to reconsider the above test.
-
This smells like a homework question!
-
Perhaps this illustration helps?
│0│1│2│3│4│5│6│7│8│9│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
╰┄╯ ╰┄╯
i=0 n=10 i=8
-
The main problem: recursion is not a reasonable approach for bubble sort, simple iteration is.
Hint: you need two loops (possibly split between two methods if you like).
Keep things simple: swap() swaps two elements, don't embed your presumptions.
public static void swap(int arr[], int i, int j)
swap(arr, 1, 2) is the same as swap(arr, 2, 1)
-
The main problem: recursion is not a reasonable approach for bubble sort, simple iteration is.
That's not true. Iteration is just a special case of recursion (tail recursion).
#include <stdio.h>
void foo(int n){
for (int i=n; i>0; --i){
printf("%d\n", i);
}
}
void bar(int n){
if (n>0){
printf("%d\n", n);
bar(n-1);
}
}
Compiled for ARM with -O2 (same result for x86, RISC-V, etc)
00000000 <foo>:
0: b538 push {r3, r4, r5, lr}
2: 1e04 subs r4, r0, #0
4: dd08 ble.n 18 <foo+0x18>
6: 4d05 ldr r5, [pc, #20] ; (1c <foo+0x1c>)
8: 447d add r5, pc
a: 4622 mov r2, r4
c: 4629 mov r1, r5
e: 2001 movs r0, #1
10: f7ff fffe bl 0 <__printf_chk>
14: 3c01 subs r4, #1
16: d1f8 bne.n a <foo+0xa>
18: bd38 pop {r3, r4, r5, pc}
1a: bf00 nop
1c: 00000010 .word 0x00000010
00000020 <bar>:
20: b538 push {r3, r4, r5, lr}
22: 1e04 subs r4, r0, #0
24: dd08 ble.n 38 <bar+0x18>
26: 4d05 ldr r5, [pc, #20] ; (3c <bar+0x1c>)
28: 447d add r5, pc
2a: 4622 mov r2, r4
2c: 4629 mov r1, r5
2e: 2001 movs r0, #1
30: f7ff fffe bl 0 <__printf_chk>
34: 3c01 subs r4, #1
36: d1f8 bne.n 2a <bar+0xa>
38: bd38 pop {r3, r4, r5, pc}
3a: bf00 nop
3c: 00000010 .word 0x00000010
Identical.
-
Renate is correct, you should prefer iteration over using recursion.
The reason is some languages and compilers do not perform tail call optimisation, as they prioritise having accurate stack traces. Python and Go are two examples.
-
Renate is correct, you should prefer iteration over using recursion.
The reason is some languages and compilers do not perform tail call optimisation, as they prioritise having accurate stack traces. Python and Go are two examples.
Poor compilers, in the modern world.
It's very weird people complaining that tail-call optimization loses information from intermediate squashed stack frames and then recommend using iteration, which BY DEFINITION overwrites the state of variables in each iteration when you perform the next iteration.
At least when you write it as recursion you have the choice of telling the compiler whether to optimize it to iteration or not.
-
These are all modern languages.
Even Rust team couldn't see enough benefit to implementing TCO in Rust. Though there are some limited cases where it can.
https://github.com/rust-lang/rust/issues/217
-
Iteration is just a special case of recursion (tail recursion).
We can put JMP, JSR, goto, loop, iteration, recursion in a blender and make any number of statements like:
- X is a general case of Y
- Y is a degenerate case of X
-
The main problem: recursion is not a reasonable approach for bubble sort, simple iteration is.
This was obviously not the "main" problem. It looked like a school assignment, which it likely was. The reason they were given this assignment is probably as an exercise to learn recursion. Wether the exercise itself is relevant is up to the teacher, I guess. But I'd say, when you start teaching students recursion, after the "obligatory" Fibonacci function, I guess you need to find a bit more involved examples that are still simple to understand, and linked to basic algorithms. So this exercise is not unreasonable IMHO.
Anyway, as said above, modern and decent compilers will likely optimize this and yield an iterative version anyway. But this is certainly not guaranteed in the general case.
I personally would not write such a function as a recursive one, but as I said above, I'm sure it was just meant as a learning exercise, and learning about recursion is worth it. Recursion is a pretty fundamental concept when it comes to algorithmics. Of course after this learning step, the teacher should definitely tell students that writing this iteratively usually makes more sense - but it would still all depend on the programming language, the compiler and possibly other factors. Actually, teaching how to transform a recursive function (when at all possible) into an iterative one is usually a step after teaching basic recursion. One thing at a time.
And all that aside, I'll comment your assertion further, in a more general way. When dealing with a "bug" (not just with software either, can be with hardware too), I personally think it's always best to fully understand it before deciding to change anything. It could be fixing the issue directly (like here, fixing the out-of-bounds issue), or a change of approach (as you'd suggest). But deciding to work around a bug just by changing the approach while not fully understanding what was wrong is, in general, a very bad idea IMHO. I'm saying this because I have actually witnessed this attitude quite a few times over the years. The first step about fixing a bug is always to understand it.
-
This was obviously not the "main" problem. It looked like a school assignment, which it likely was. The reason they were given this assignment is probably as an exercise to learn recursion. Wether the exercise itself is relevant is up to the teacher, I guess. But I'd say, when you start teaching students recursion, after the "obligatory" Fibonacci function, I guess you need to find a bit more involved examples that are still simple to understand, and linked to basic algorithms. So this exercise is not unreasonable IMHO.
I agree.
Anyway, as said above, modern and decent compilers will likely optimize this and yield an iterative version anyway. But this is certainly not guaranteed in the general case.
You can expect it of any recent (Last decade? More?) version of gcc or llvm or comparable quality compilers.
I personally would not write such a function as a recursive one, but as I said above, I'm sure it was just meant as a learning exercise, and learning about recursion is worth it. Recursion is a pretty fundamental concept when it comes to algorithmics. Of course after this learning step, the teacher should definitely tell students that writing this iteratively usually makes more sense - but it would still all depend on the programming language, the compiler and possibly other factors. Actually, teaching how to transform a recursive function (when at all possible) into an iterative one is usually a step after teaching basic recursion. One thing at a time.
I *absolutely* would write this as recursive. Every time.
Iteration is a little more compact and is acceptable for the very simplest loops -- a simple iteration over every element of an array to print it, for example. Or a trivial while loop with a simple exit condition.
But for anything more complex it's FAR EASIER to reason about recursion and to prove that it is correct, because you use static stateless reasoning not dynamic reasoning. You don't need to worry about "this variable has this value and then later it has this value". You just solve one sub-problem and then solve the next sub-problem.
#include <stdio.h>
void swap(int *a, int *b){
int t = *a; *a = *b; *b = t;
}
// move the biggest element to *hi
void bubble_up(int *lo, int *hi){
if (lo >= hi) return;
if (lo[0] > lo[1]) swap(lo, lo+1); // make sure the first item is not bigger than the second one
bubble_up(lo+1, hi); // move the biggest element in the rest to *hi
}
void bubble_sort(int *lo, int *hi){
if (lo >= hi) return;
bubble_up(lo, hi); // move the biggest element to *hi
bubble_sort(lo, hi-1); // sort the rest below hi
}
int main(){
int arr[] = {234, 2, 656, 45665, 2324, 768, 345, 3, 765};
bubble_sort(arr, arr+8);
for (int i=0; i<9; ++i) printf("%d\n", arr[i]);
return 0;
}
With gcc and -O2 this compiles to a quite lovely and compact function in machine code:
000101f6 <bubble_sort>:
101f6: 00b57f63 bgeu a0,a1,10214 <bubble_sort+0x1e>
101fa: 87aa mv a5,a0
101fc: 4398 lw a4,0(a5)
101fe: 43d4 lw a3,4(a5)
10200: 00e6d463 bge a3,a4,10208 <bubble_sort+0x12>
10204: c394 sw a3,0(a5)
10206: c3d8 sw a4,4(a5)
10208: 0791 addi a5,a5,4
1020a: feb7e9e3 bltu a5,a1,101fc <bubble_sort+0x6>
1020e: 15f1 addi a1,a1,-4
10210: feb565e3 bltu a0,a1,101fa <bubble_sort+0x4>
10214: 8082 ret
What could possibly be clearer?
-
It's really a shame that generations of teachers have been telling students that recursion is scary and hard and dangerous and they have to learn just a little about it so they can pass their exams but they shouldn't ever use it afterwards.
It's simply not true today.
It's like how motorcycle instructors tell beginning riders to ride in the car wheel tracks, not between them. Which is just plain bad advice.
Why?
It's because a lifetime ago cars weren't made very well and were constantly dripping oil everywhere and this made the part of the road between the wheel tracks oily and slippery, especially if it starts to rain. Modern cars don't do that, and the part of the tar that car wheels don't go on much is pristine and grippy and isn't breaking up and doesn't have potholes.
-
I *absolutely* would write this as recursive. Every time.
Okey-doke. Just remember to disassemble it to make sure that your -O2 worked.
It's really a shame that generations of teachers have been telling students that recursion is scary and hard and dangerous...
Many student problems (factorial, Fibonacci, GCD) are given with a recursive definition and proud students implement it as such to prove how clever they are.
Clever is having enough insight to implement them iteratively.
Sure, there are plenty of problems that recursion simplifies things.
Without recursion you'd have to explicitly generate a data stack.
That is, unless we are talking about something so trivial that it does not even require that.
-
I *absolutely* would write this as recursive. Every time.
Okey-doke. Just remember to disassemble it to make sure that your -O2 worked.
With things that *could* be written using iteration you don't need to check. Disassembly is just for illustrative purposes.
It's really a shame that generations of teachers have been telling students that recursion is scary and hard and dangerous...
Many student problems (factorial, Fibonacci, GCD) are given with a recursive definition and proud students implement it as such to prove how clever they are.
Clever is having enough insight to implement them iteratively.
Clever is writing easy to understand code and letting the computer do the hard work for you.
Sure, there are plenty of problems that recursion simplifies things.
Without recursion you'd have to explicitly generate a data stack.
That is, unless we are talking about something so trivial that it does not even require that.
Anything that can be written with loops with complicated variable updating or multiple exit conditions is better and more clearly written with tail recursion instead.
It doesn't need a stack either way.
Both students and professionals get loops and loop exit conditions wrong all the time. Loops and destructive assignment are *hard*. Unless the loop is trivial you're probably not going to get it right first time unless you explicitly think about and preferably write down (maybe in assert()s) loop invariant, pre-condition, and post-condition.
Or, you can use recursion.
-
It's really a shame that generations of teachers have been telling students that recursion is scary and hard and dangerous and they have to learn just a little about it so they can pass their exams but they shouldn't ever use it afterwards.
I personally have never been taught that - in my uni years anyway. As I remember, recursion was taught as a fundamental approach that was (but for the simplest algorithms) often more elegant than an iterative version, easier to read and easier to prove correct as well (if used properly of course). But maybe I'm biased because I took CS classes, that I found interesting at the time (that's when I got to know about Knuth). "Software engineering" classes were something else, and that's more often where you'd hear such things.
The "scary and dangerous" part, IME, appeared once you got a job in an industrial setting. People there would tell you such things, and if you work in certain regulated environments, it's even part of some hard-written rules that you can't get away from.
Of course it's linked to the languages used (and the associated memory models), more so than to the principle of recursion itself, how function calls are implemented, how call stacks are implemented, and so on, so that's something you often hear when using C (even though it's not always justified IMO), but with some other languages - such as functional languages - recursion can be an integral part of them and is not seen as posing problems per se.
-
It doesn't need a stack either way.
Real recursion needs a stack of some kind, either implicitly the program stack or explicitly somewhere else.
I have nothing against real recursion (and I use it often), just gratuitous tail recursion.
*Real = something that can not be written as tail recursion.
You seem to like tail recursion. We'll have to leave it at that.
-
It doesn't need a stack either way.
Real recursion needs a stack of some kind, either implicitly the program stack or explicitly somewhere else.
I have nothing against real recursion (and I use it often), just gratuitous tail recursion.
*Real = something that can not be written as tail recursion.
Recursion is a syntactic property. You can't say that "real" recursion requires a stack, because I can show you useful recursive algorithms that will blow any stack and require a garbage-collected heap instead. I guess that must be more than "real". Trancendental?
You seem to like tail recursion. We'll have to leave it at that.
I do. It's the Ultimate GOTO.
You probably hate continuations.
-
As I said earlier, I think many people confuse recursion itself with the way recursion is implemented with a given programming language, a given compiler and a given underlying platform.
I agree with Bruce. Recursion can be implemented in various ways. As I also said before, in some programming languages, a number of things are just NOT doable unless you use "recursion", and they don't necessarily use simple stacks either.
BUT - it is also true that in some prog. languages, especially those commonly used in the embedded world (such as C), recursion is most often implemented with the "stack", unless, as Bruce mentioned, it is just tail recursion, in which case decent modern compilers will optimize that and yield an iterative version. But it still depends on the optimization level, and still, less obvious recursion patterns are likely not to be optimized and still use the "stack". Then, whether this is a problem or not really depends on the underlying platform. But admittedly, it is pretty common with the typical C "memory model" that the "stack" be (often much) more limited in size than the "heap", and furthermore used both for data AND as a call stack (which IMO is a disastrous design choice, leading to a gigantic number of potential dangerous bugs and exploits, but that's another story), hence all the cautiousness with using recursion.
-
But admittedly, it is pretty common with the typical C "memory model" that the "stack" be (often much) more limited in size than the "heap", and furthermore used both for data AND as a call stack (which IMO is a disastrous design choice, leading to a gigantic number of potential dangerous bugs and exploits, but that's another story), hence all the cautiousness with using recursion.
The mighty 6502 got it right! 256 bytes of stack ought to be enough for anyone for function return addresses.
If you're doing the kind of recursion where each function calls itself more than one time such as traversing a tree or doing quicksort then the number of calls and the execution time explodes extremely rapidly with the stack depth used. Put the other way around, with any reasonable amount of data and execution time, the stack depth needed is very limited, provided only that the call structure is reasonably balanced. If your binary tree is close to being a linear list then all bets are off. Or if your Quicksort initially recurses on the larger remaining partition instead of the sensible first recursing on the smaller of the two partitions and then tail-recursing on the larger one.
It just comes down to knowing your algorithm and knowing your data structure and using sensible ones. Which you should be doing *anyway*.
-
So this exercise is not unreasonable IMHO.
Meh. A recursion exercise ought to solve a problem that is easier to visualize as recursive. Bubble sort isn't, IMO.Something with trees would be much better (and a good intro to things that are likely to follow in the educational path!) (although, this assignment could pre-date the introduction of the data structures needed to elegantly implement trees. Maybe a binary search?)
-
Quicksort is the traditional recursive exercise.
-
Quicksort is the traditional recursive exercise.
It is, but that's usually just teaching recursion as an implementation hack "look, you don't need to make an array and manage remembering the partition you can't sort right away by implementing a stack in it" instead of as a way to THINK about problems.
Using recursion for bubble sort makes it clear that you can think about the same algorithm as either
- sort an array by moving the smallest item to the start of the array, then moving the next smallest to the 2nd position, and so on
or
- an array sorted IS the smallest item in the array FOLLOWED BY the other items sorted.
And the second way is easier to think about, to implement, and to prove correct.
-
Agree again with Bruce, although I do think Quicksort is also a good candidate for that (and I kind of see he seems obsessed with tail recursion specifically - no offense intended, just a note). It is actually conceptually easier to define any kind of sorting algorithm with recursion, and also easier to prove why it works IMHO.
When you deal with iterative algorithms, you can (I should say SHOULD) use invariants to both help implementing them and prove the implementation is correct.
If you think about it, an invariant is usually nothing more than a form of recursive expression.
A sequence of unrelated steps is a different beast of course, but as soon as you use iteration with results that depend, at each iteration, on the previous iterations, then it is definitely a recursive definition. Then iterative vs. recursive from a coding POV is just an implementation choice, which may depend on a number of factors (including not having a choice with some languages as I already mentioned.)
-
When you deal with iterative algorithms, you can (I should say SHOULD) use invariants to both help implementing them and prove the implementation is correct.
Absolutely.
Precondition, postcondition, and loop invariant (which reduces to the precondition and the postcondition at the start and at the finish).
If your loop is simple enough that you don't need to think about and preferably write down in at least a comment if not an assertion then it's a rather trivial loop and really doesn't matter how you write it (and probably expressible with a simple "each" or "forall" or whatever your language provides).
Much of modern programming, of course, involves hiding all non-trivial loops from the programmer, by burying them inside a standard data structure or standard algorithm in the language's library.
-
I personally would prefer the second lesson on recursion (examining the exercises like the OP is asking about) to concentrate on the possible errors, like one-off errors and infinite recursion.
This shows the learners that while there is more than one way to implement something, there are vastly more ways to do it wrong.
Then, later on, when the learner has sufficient practical experience to understand the theoretical underpinnings, they'll both have something to anchor theory on, but also understand that the theory is inherently useful: one does not need to know all the ways things can go wrong, or each of the ways to do it right, if they have tools to prove the solution right/wrong. It's not theory for the sake of knowing the theory, it is a set of meta-tools for development.
I always like to rely on (my) inherent laziness. True laziness is when the overall workload is minimized; not when necessary work is postponed or pushed to others, minimizing just the immediate workload. The latter is just being short-sighted, shitty dev. (Yes, even if your employer demands you do that. They are then deliberately paying you to be a shitty dev. It's a very common and perfectly valid occupation, but produces shit products. Which often sell well, given big enough marketing budgets.)
In this thread, as so often happens in this sub-forum, we've delved deep into the theory and details, without showing the OP or others how it is related to the question at hand.