использавание рекурсии вместо цикла

[alina44]

Помогите, пожалуйста!
Нужно использовать рекурсию вместо цикла:

#include <iostream>
using namespace std;
int a[100], b[100], n;
 
int digit(int n, int p)
{
    return (n >> p & 1);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int k = sizeof(int);
    for(int i = 0; i < k; i++)
    {
        int c[2] = {0};
        for(int j = 0; j < n; j++)
            c[digit(a[j],i)]++;
        for(int j = 1; j < 2; j++)
            c[j] += c[j - 1];
        for(int j = n - 1; j > -1;j--)
            b[--c[digit(a[j],i)]] = a[j];
        for(int j = 0; j < n; j++)
            a[j] = b[j];
    }
    for(int i = 0; i < n; i++)
        cout << a[i] <<endl;
    return 0;
}

Пыталась переделать, но что-то пошло не так...

#include <iostream>
 
void out(int n, int t, int* &arr){
    std::cout << "Enter " << n + 1 << " element: " << std::endl;
    std::cin >> arr[n];
    if (n < t - 1) out(++n, t, arr);
}
 
void out_sort(int n, int t, int* arr){
    std::cout << "arr[" << n + 1 << "]=" << arr[n] << std::endl;
    if (n < t - 1) out_sort(++n, t, arr);
}
 
void sort1(int countofbits, int n, int t, int* arr, int &count0){
    if (arr[n] >> countofbits & 1 == 0)
        count0++;
    if (n < t - 1) sort1(countofbits, ++n, t, arr, count0);
}
 
void sort2(int i, int t, int* arr, int* &mirrow, int countofbits, int &count0, int &count1){
    mirrow[--((arr[i] >> countofbits & 1 == 0) ? (count0) : (count1))] = arr[i];
    if (i > 0) sort2(--i, t, arr, mirrow, countofbits, count0, count1);
}
 
void sort3(int i, int t, int* &arr, int* mirrow){
    arr[i] = mirrow[i];
    if (i < t - 1) sort3(++i, t, arr, mirrow);
}
 
void sort(int countofbits, int t, int* &arr){
    int count0, count1;
    count0 = 0;
    count1 = t;
    sort1(countofbits, 0, t, arr, count0);
    int* mirrow = (int*)malloc(t*sizeof(int));
    sort2(t, t, arr, mirrow, countofbits, count0, count1);
    sort3(0, t, arr, mirrow);
    if (countofbits < 8 * sizeof(int)) sort(++countofbits, t, arr);
}
 
int main() {
    int t;
    std::cout << "Enter n: " << std::endl;
    std::cin >> t;
    int* arr = (int*)malloc(t*sizeof(int));
    out(0, t, arr);
    sort(0, t, arr);
    out_sort(0, t, arr);
    system("pause");
    return 0;
}

[Stilet]

А как задание звучит?

[alina44]

реализовать битовую сортировку без использования циклов

[Stilet]

Э-э-эм... Я немного от темы отойду: Ты свой код запускала? Он у тебя вообще нормально сортирует?

[alina44]

выводит число -33686019

[Stilet]

Не, я имел ввиду твой первый код с циклами.
Я его запустил, но не увидел чтоб выходной поток сортировался.
Или же я не понимаю алгоритма такой сортировки.

[alina44]

1-й работает и сортирует

n >> p & 1
Мы сдвигаем число вправо что бы нужный нам бит стал первым, а потом получаем его с помощью логического "и" с 1
for(int j = 0; j < n; j++)
c[digit(a[j],i)]++; // подситываем количсетво каждой из цифр
for(int j = 1; j < 2; j++)
c[j] += c[j - 1]; // устанавливаем позиции, на которых должны располагаться числа с заданными цифрами
for(int j = n - 1; j > -1;j--)
b[--c[digit(a[j],i)]] = a[j]; // расставляем в соответствии с цифрой
for(int j = 0; j < n; j++)
a[j] = b[j];

[Stilet]

От я опоссум )))
Старею видать, мозги совсем не варят...
Вот, смотри. Рекурсия такая подойдет?:

// Битовая сортировка.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

const int n=10;
int a[n]={1,5,2,3,7,8,9,2,4,43}, b[n];
int c[2] = {0};
 
int digit(int n, int p)
{
    return (n >> p & 1);
}

void for1(int i,int j, int n){
 if(j==n) return;
 c[digit(a[j],i)]++;
 for1(i,j+1,n);
}

void for2(int i,int j){
 if(j==-1) return;
 b[--c[digit(a[j],i)]] = a[j];
 for2(i,j-1);
}

void for3(int i,int j){
 if(j==-1) return;
 b[--c[digit(a[j],i)]] = a[j];
 for2(i,j-1);
}

int _tmain(int argc, _TCHAR* argv[])
{
	
	int i=0;

    int k = sizeof(int);
    for(int i = 0; i < k; i++)
    {
		memset(&c[0],0,sizeof(c));
		for1(i,0,n);
		c[1]+=c[0];
		for2(i,n-1);
		memcpy(&a[0],&b[0],sizeof(int)*n);
    }

    for(int i = 0; i < n; i++)
        cout<<a[i]<<'\t';
	system("pause");
    return 0;
}

[alina44]

Да, спасибо большое