Рекурсивная программа

[Alexandr-]

Напишите рекурсивную программу для сортировки массива методом "пузырька".

Как сделать из простого кода пузырька рекурсивную программу? Как понимаю нужно запихать ее в какую-то функцию, но явно не просто так...

#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;
int main() {
	int i,j,c,n; int *A;
	printf ("vvedite razmer massiva\n");
	scanf ("%d",&n);
	srand(time(NULL));
	 A=(int *)malloc(n*sizeof(int));
	 printf ("massiv do\n");
	for (i=0;i<n;i++) {A[i]=rand()%100-20;  printf ("%d ", A[i]); }

	for (i=0;i<n-1;i++)
		for (j=n-2;j>=i;j--)
			if (A[j]>A[j+1]) {
				c=A[j]; A[j]=A[j+1];
				A[j+1]=c; }
			printf ("\nmassiv posle\n");

			for (i=0;i<n;i++) {printf ("%d ",A[i]); }

free (A);
system("pause"); return 0; }

[Nuklon]

#include <ostream>



void bsort(int* A, int N) {
    bool go = false;
    for(int i = 0; i < N - 1; i++) {
        if(A[i] > A[i + 1]) {
             int tmp  = A[i];
             A[i]     = A[i + 1];
             A[i + 1] = tmp;
             go = true;
        }
    }

    if(go)
        bsort(A, N);
}




int main(void){
    int a[] = { 10, 5, -1, 8, -2, -3, 1, 0, 4, 7 };
    int n   = sizeof(a)/sizeof(a[0]);

    bsort(a, n);
    for(int i = 0; i < n; i++)
        std::cout << a[i] << ' ';
    return 0;
}

http://codepad.org/eKxNnCJM

[Alexandr-]

А в чем заключается рекурсия, ведь программа выполняется, как обычно?

[Stilet]

ведь программа выполняется, как обычно?

Обрати внимание: В конце процедуры написано:

void bsort(int* A, int N) {
...
    if(go)
        bsort(A, N);
}

Функция вызывает саму себя.

[Alexandr-]

Пытался разобраться, но так и не понял, что значат эти строки:
bool go = false;
go = true;
Помогите разобраться до конца.

[Stilet]

Как я понимаю:
После вызова функции, ее тело прежде всего проводит некую сортировку, судя по всему зупырьком. Обычно это делается двумя циклами, потому что по массиву нужно проводить проход несколько раз - такова механика пузырька (при сортировке перемещается только один элемент). В этом цикле, перемещающем этот элемент (не обязательно один и тот же - просто могут меняться соседние элементы) ставится флаг go, который изанчально сигнализирует о том что сортировка не нужна (bool go = false, ибо если это так условие в цикле не будет выполняться (ну действительно зачем сортировать то что уж отсортированно).
Однако если хотя бы один раз условие выполнится, это будет означать что некий элемент поменялся местами с соседом, и возможно (скорее всего) требуется его подальшее продвижение вверх. Не важно сколько таких элементов будет все равно этот флаг будет установлен в true при выявлении первого из таких элементов. Соответственно условие после цикла будет решать - был ли найден при сортировке хотя бы один такой элемент, который пришлось переставлять, и запустит эту же функцию еще раз, дабы она продолжила перестановку.
Пока в массиве будут выявляться передвижения - функция будет запускать саму себя для сортировки. Как только такие передвижения закончатся функция многократно выйдет из самой себя и завершит работу вовсе.
Это все наглядно может проиллюстрировать пошаговая отладка - там посмотришь как "всплывают" по телу массива сортируемые элементы.