Что не так в этой рекурсии?

Question

[HonestHacker]

есть массив. нужно найти рекурсивно произведения его множителей. путём деления пополам массива. но рекурсивные вызовы должны остановиться если кусок массива с которым работаем состоит из одного или двух элементов.

int recursion(int* X, int N, int i, FILE* res)
	{
		if (N - i == 2) 
			return X[i] * X[i+1];

		if (N - i == 1)
			return X[i];

			int N1 = N/2;
			int i2 = N - N1 + 1;

			return (recursion(X, N1, i, res)*recursion(X, N, i2, res));
	}

fprintf(res, "%d", recursion(X, N, i, res)); вот так вывожу ответ

X- массив N - изначально длина массива

проблема в том что визуалка говорит что у меня исключение под строкой int recursion...

Comments

[Иван Клименко]

Непонятно, зачем вам указатель на файл в самой функции

[HonestHacker]

Иван Клименко, не знаю зачем, но без него не работает

Answer 1

[Иван Клименко]

Правильный вариант функции:

int mul(int * arr, int N, int shift = 0)
{
    switch (N)
    {
        case 1:
            return arr[shift];
        break;

        case 2:
            return (arr[shift] * arr[shift + 1]);
        break;

        default:
            int M = N / 2;
            return (mul(arr, M, shift) * mul(arr, N - M, shift + M));
    }
}

В вашей функции последние три строки выполняются всегда, вне зависимости от длины массива. Поэтому происходит выход за границы массива.

Comments

[Иван Клименко]

Вот так можно использовать функцию:

int array[] = {5, 4, 3, 2, 1};
int s = mul(array, 5); // s = 120

[HonestHacker]

я ввел массив состоящий из единиц. ответ получается -33686019
почему?

int recursion(int* X, int N, int i, FILE* res)
	{

		switch (N)
		{
		case 1:
			return X[i];
			break;

		case 2:
			return (X[i] * X[i + 1]);
			break;

		default:
			int M = N / 2;
			return (recursion(X, M, i, res) * recursion(X, N - M, i + M, res));
		}
	}

[Иван Клименко]

Я не знаю, почему у вас так получилось. Вот рабочий вариант

[HonestHacker]

весь код

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <conio.h>

	void readm(int &N, int* &X, FILE* dat)   // & тут потому что ни N ни X внутри main не меняются, 
	{                                         // потому что их новое значения не возвращаются из функции readm
		scanf("%d", &N);
		X = new int [N];
		for (int i = 0; i < N; i++)
		{
			fscanf(dat, "%d", &X[i]);
		}
	}

	void writem(int N, int* X, FILE* res)
	{
		for (int i = 0; i < N; i++)
		{
			fprintf(res, "%d ", X[i]);
		}
	}

	int recursion(int* X, int N, int i, FILE* res)
	{

		switch (N)
		{
		case 1:
			return X[i];
			break;

		case 2:
			return (X[i] * X[i + 1]);
			break;

		default:
			int M = N / 2;
			return (recursion(X, M, i, res) * recursion(X, N - M, i + M, res));
		}
	}



int main(int argn, char* argc[])
{
	FILE* dat, * res;
	dat = fopen(argc[1], "r");
	res = fopen(argc[2], "w");
	int N = 0;
	int i = 1;
	int *X = nullptr;
	readm(N, X, dat);
	//writem(N, X, res);
	//recursion(X, N, i, res);
	fprintf(res, "%d", recursion(X, N, i, res));
	return 0;
}

[Иван Клименко]

HonestHacker, всё равно ничего не понятно. Что у вас внутри файлов мне неизвестно.

К тому же вы так и не ответили, зачем вы передаёте указатель на файл внутрь функции, а потом не используете его.

В качестве совета -- если вы пишите на C++, то пишите на нём полностью, а не вперемешку с древним C.

P. S. изначально переменная i должна быть равна нулю.

[jcmvbkbc]

В вашей функции последние три строки выполняются всегда, вне зависимости от длины массива.

Иван Клименко, неверно, при длине 1 и 2 происходит возврат из функции до рекурсивного вызова.

вы присваиваете переменной N ноль внутри функции main. А потом нигде не меняете его.

Опять неверно, меняет в первой строке функции readm.

[Иван Клименко]

jcmvbkbc, с первым я погорячился, да. А второе исправил сразу же =)

[HonestHacker]

Иван Клименко, действительно, i изначально должно было равняться нулю. теперь работает

Answer 2

[jcmvbkbc]

Что не так в этой рекурсии?

Она выглядит непонятно. Её можно переписать понятно так:

int mul(const int *x, int n)
{
    assert(n > 0);
    if (n == 1)
        return x[0];
    if (n == 2)
        return x[0] * x[1];
    return mul(x, n / 2) * mul(x + n / 2, n - n / 2);
}

Comments

[HonestHacker]

я изначально делал упрощённую версию кода с возможностью добавления остальных деталей. твой код сильно отличается от моего. его невозможно модернизировать. поэтому отмечу решением другую работу, которая идеально подошла.
а так код хороший