how to swap 2 variables using recursion

Question

i've tried to swap 2 variables using recursion.So i passed them by reference and nothing change in the main frame. But inside the function scope it works...Can anyone explain me how this code works inside the stack and if is there any other solution to swap varibles using recursion?

#include <iostream>

void swap(int &a, int &b) {
    if (a>b)
    {
        swap(b,a);
    }

}

int main()
{
    int x = 10;
    int y = 8;;
    swap(x, y); 
    std::cout << x << ' ' << y;
    return 0;

}

I know there are other solutions easier like using 3rd variable or using std::swap() or using ^= but i want to understand why nothing changed even i passed it by reference — aslam louati, Dec 03 '22 at 20:12
Your `swap` function calls itself if `a > b` but does nothing in any other case. The values aren't swapped because your function doesn't swap anything. — Retired Ninja, Dec 03 '22 at 20:17
What line of this code do believe performs the swap? The only thing your `swap` function ever does is call itself again. — Drew Dormann, Dec 04 '22 at 02:54
@aslamlouati _"but I passed by reference....it should be swapped"_ - if `a>b` you _will_ call `swap` again (recursively) with the parameters swapped - but you are never actually swapping the values like ggorlen pointed out in the answer you've gotten. Did the answer help to clear up the confusion? If so, please consider accepting it. If not, you may ask for clarification in the comment section under the answer. — Ted Lyngmo, Dec 16 '22 at 09:51

ggorlen · Answer 1 · 2022-12-04T02:58:04.720

Simply switching the parameters in the recursive call doesn't actually swap the values of the variables in the caller, or anywhere else. There's no (sensible) way to write this recursively because swapping isn't a recursive procedure. Recursion is used when you're traversing a data structure with multiple elements, like an array or a tree, or you're manipulating numbers repeatedly over time, as in a Fibonacci sequence.

But here, there's no repeated decision to be had. All it is is "swap if a > b, otherwise don't", which is a simple if, plus one of the normal swapping approaches you described:

#include <iostream>

void swap_if_greater(int &a, int &b) {
    if (a > b) {
        std::swap(a, b);
    }
}

int main() {
    int x = 10;
    int y = 8;
    swap_if_greater(x, y);
    std::cout << x << ' ' << y; // => 8 10
}

Note that I've renamed the function. swap implies an unconditional swap, but that's not what the function does. The function ensures the lower value will be in the first argument, so it's been renamed to swap_if_greater to reflect that. If you do want an unconditional swap, use std::swap.

how to swap 2 variables using recursion

1 Answers1