Я не понимаю, как писать функции рекурсивно - PullRequest
Новая
       11

Я не понимаю, как писать функции рекурсивно

0 голосов
/ 14 апреля 2019

Так что мне нужно вызывать одну функцию рекурсивно в другой функции. У меня есть массив и первые 2 параметра в функции указатели на начало массива и за его концом. Третий параметр - это функция, которую мне нужно вызывать рекурсивно, а 4-й параметр - это значение по умолчанию, которое я назвал a_0; Предположим, что массив имеет элементы: a_1, a_2, a_3, ... , a_n. Моя функция Результат нужно рассчитать так: 

f(...f(f(f(a_0,a_1),a_2),a_3),...,a_n)

Это задание для практики, для экзамена, и я действительно не понимаю принцип рекурсии (я понимаю для Факториала), но я не понимаю этот пример. 

 int Result(int *p, int *q,int (*f)(int, int), int a_0=0) {
      //I need to return this: f(...f(f(f(a_0,a_1),a_2),a_3),...,a_n)
 }

1 Ответ

0 голосов
/ 14 апреля 2019

Это «левый сгиб»;Вы можете прочитать об этом во многих местах онлайн.

На каждом шаге a_0 должно быть значением, «накопленным» до настоящего времени;то есть, если входной массив равен arr и начальное значение a0, его значения равны 

a0
f(a0, arr[0])
f(f(a0, arr[0]), arr[1])
f(f(f(a0, arr[0]), arr[1]), arr[2])
...

"a_0" - не очень хорошее имя, так как это только очень редко начальное значение, поэтомуЯ переименую его в «аккумулятор».

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

int Result(int *p, int *end, int (*f)(int, int), int accumulator=0) 
{
    if (p >= end)
    {
        return accumulator;
    }
    else
    {
        // To be determined
    }
}

Для рекурсивного случая - то есть фактического вычисления результата - вам нужно использовать аккумулятор и текущий элемент (*p или p[0]), чтобы создать новое значение для передачи,и затем выполнить рекурсию по остальной части массива 

int Result(int *p, int *end, int (*f)(int, int), int accumulator=0) 
{
    if (p >= end)
    {
        return accumulator;
    }
    else
    {
        return Result(p + 1, end, f(accumulator, *p));
    }
}

или, короче 

int Result(int *p, int *end, int (*f)(int, int), int accumulator=0) 
{
    return p >= end
          ? accumulator
          : Result(p + 1, end, f(accumulator, *p));
}
...