Рекурсия Вопрос: Редакция

Question

Мои слайды говорят, что:

• Рекурсивный вызов должен быть всегда на меньшем структуры данных, чем текущая

• Там должно быть не рекурсивный вариант, если структура данных слишком мал

• Вам нужен метод обертки, чтобы сделать рекурсивный метод доступного

Просто прочитав это со слайдов, нет смысла, особенно видя, что это была тема от Рождества!

Может ли кто-нибудь попробовать и прояснить, что это значит, пожалуйста?

Спасибо

Answer 1

recurssive вызов должен быть всегда на меньшем структуры данных, чем текущая

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

Возьмите, к примеру, Quicksort. Каждый раз, когда функция вызывается, она работает с меньшим набором данных.

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

void printList(List l){ 
    print(l.head); 
    printList(l.tail); 
} 

там должно быть не recurssive вариант, если структура данных слишком мал

Это означает, что должен быть базовый случай. Точка, в которой функция перестает называть себя снова.

int factorial(int n){ 
    if (n == 1){ //the base case is when n = 1 
     return 1; 
    } 
    return n*factorial(n-1); 
} 

Возвращаясь к примеру печати связного списка, должен быть случаем, когда у вас есть только пустой список влево (в этом случае функция не должна делать ничего). Возвращаясь к коду для печати Связанного списка

void printList(List l){ 
    if (l.empty == true){ //the base case is when the list l is empty 
     return; 
    } 

    print(l.head); 
    printList(l.tail); 
} 

вам нужен метода обертки, чтобы сделать recurssive метод доступного

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

У вас может быть функция обертки, которая упрощает параметры только для того, что необходимо. Затем функция-обертка вызывает действительную рабочую функцию.

Примером может быть, если у нас есть связанный класс списка, который имеет рекурсивную функцию для печати списка. Его заявление будет выглядеть примерно так:

void printList(List l); 

Однако, как это метод класса, к кому-то, используя API это не имеет большого Sence, чтобы сделать это:

myList.printList(myList); 

Так может быть создана функция-оболочка, которая не имеет параметров, которые затем вызывают код, выполняющий эту работу.

void printList(){ 
    doPrintList(this); //pass in the List object as the first argument 
} 

Тогда все программатор с помощью API должен сделать:

myList.printList();