1 Востаннє редагувалося Q-bart (23.02.2015 18:21:27)

Тема: Рекурсія

Вітаю.
Стикнувся з такою штукою, як рекурсія... Почитав про неї, подивився приклад рекурсії при розрахунку факторіалу... Здавалось, би зрозумів. Та все таки не в'їхав. Вирішив не використовувати її. Та все ж стикнувся з завданням де треба рекурсію...

завдання

Розробити функцію file_search(folder, filename),
яка приймає 2 аргументи -- список folder та рядок filename,
та повертає рядок -- повний шлях до файлу або папки filename в структурі folder.

Файлова структура folder задається наступним чином:

Список -- це папка з файлами, його 0-й елемент містить назву папки, а всі інші можуть представляти або файли в цій папці (1 файл = 1 рядок-елемент списку), або вкладені папки, які так само представляються списками. Як і в файловій системі вашого комп'ютера, шлях до файлу складається з імен всіх папок, в яких він міститься, в порядку вкладеності (починаючи з зовнішньої і до папки, в якій безпосередньо знаходиться файл), розділених "/".

Вважати, що імена всіх файлів є унікальними. Повернути логічне значення False, якщо файл не знайдено.

Наприклад
Виклик функції: file_search(['C:', 'backup.log', 'ideas.txt'], 'ideas.txt')
Повертає: 'C:/ideas.txt'

Я думав робити так.. Функція перевіряє кожний елемент списку. Якщо знаходить шуканий файл - виводить,..
А якщо елемент - список, то ще раз треба викликати функцію...

code
def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            way_to_file =  '/' + filename
        elif type(i) == list :
            file_search(i, filename)
            
    return way_to_file

Та код не працює... Або я не розумію про рекурсію і що не вистачає в коді або неправильний алгоритм..

2

Re: Рекурсія

Q-bart написав:

Вітаю.
Стикнувся з такою штукою, як рекурсія... Почитав про неї, подивився приклад рекурсії при розрахунку факторіалу... Здавалось, би зрозумів. Та все таки не в'їхав. Вирішив не використовувати її. Та все ж стикнувся з завданням де треба рекурсію...

завдання

Розробити функцію file_search(folder, filename),
яка приймає 2 аргументи -- список folder та рядок filename,
та повертає рядок -- повний шлях до файлу або папки filename в структурі folder.

Файлова структура folder задається наступним чином:

Список -- це папка з файлами, його 0-й елемент містить назву папки, а всі інші можуть представляти або файли в цій папці (1 файл = 1 рядок-елемент списку), або вкладені папки, які так само представляються списками. Як і в файловій системі вашого комп'ютера, шлях до файлу складається з імен всіх папок, в яких він міститься, в порядку вкладеності (починаючи з зовнішньої і до папки, в якій безпосередньо знаходиться файл), розділених "/".

Вважати, що імена всіх файлів є унікальними. Повернути логічне значення False, якщо файл не знайдено.

Наприклад
Виклик функції: file_search(['C:', 'backup.log', 'ideas.txt'], 'ideas.txt')
Повертає: 'C:/ideas.txt'

Я думав робити так.. Функція перевіряє кожний елемент списку. Якщо знаходить шуканий файл - виводить,..
А якщо елемент - список, то ще раз треба викликати функцію...

code
def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            way_to_file =  '/' + filename
        elif type(i) == list :
            file_search(i, filename)
            
    return way_to_file

Та код не працює... Або я не розумію про рекурсію і що не вистачає в коді або неправильний алгоритм..

Якщо використовуєте рекурсію, то не просто викликайте функцію зсередини, а повертайте результат такого виконання.

code
def file_search(folder, filename):
    for i in folder :
        if i == filename:
            return  '/' + filename
        elif type(i) == list :
            return file_search(i, filename)

Ніби так, але нічого не гарантую.

Подякували: Q-bart1

3 Востаннє редагувалося yarko (23.02.2015 18:50:01)

Re: Рекурсія

Пропоную замість рекурсії використати чергу.
Тобто якщо виникає необхідність пошукати у підпапці, то поміщати дані про цю підпапку в кінець черги. Якщо в поточному елементі черги (конкретна папка) шуканого файлу не знайдено, то брати наступний елемент і т.д., доки в черзі є дані. Так принаймні ви не заплутаєтесь у стеку викликів. І черга вигідніша в машинному часі.

Подякували: Q-bart1

4

Re: Рекурсія

yarko написав:

Пропоную замість рекурсії використати чергу.
Тобто якщо виникає необхідність пошукати у підпапці, то поміщати дані про цю підпапку в кінець черги. Якщо в поточному елементі черги (конкретна папка) шуканого файлу не знайдено, то брати наступний елемент і т.д., доки в черзі є дані. Так принаймні ви не заплутаєтесь у стеку викликів. І черга вигідніша в машинному часі.

Тут не завадив би пруф про вигідність. І як ви можете заплутатись в стеку викликів?

5 Востаннє редагувалося P.Y. (23.02.2015 19:08:49)

Re: Рекурсія

quez написав:

Якщо використовуєте рекурсію, то не просто викликайте функцію зсередини, а повертайте результат такого виконання.
...
Ніби так, але нічого не гарантую.

Не годиться — так пошук пропускатиме все, що йде після першої підпапки.
Крім того, шлях до файлу має враховувати ім'я папки.

code
def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            return  way_to_file + '/' + filename
        elif type(i) == list :
            found_file=file_search(i, filename)
            if found_file!=None:
                return way_to_file + '/' + found_file
Подякували: Q-bart1

6

Re: Рекурсія

P.Y. написав:
quez написав:

Якщо використовуєте рекурсію, то не просто викликайте функцію зсередини, а повертайте результат такого виконання.
...
Ніби так, але нічого не гарантую.

Не годиться — так пошук пропускатиме все, що йде після першої підпапки.
Крім того, шлях до файлу має враховувати ім'я папки.

code
def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            return  way_to_file + '/' + filename
        elif type(i) == list :
            found_file=file_search(i, filename)
            if found_file!=None:
                return way_to_file + '/' + found_file

З другим зауваженням згоден, з першим ні.

7 Востаннє редагувалося P.Y. (23.02.2015 19:16:24)

Re: Рекурсія

Якщо в папці є дві підпапки, і те, що ми шукаємо, лежить у другій, то як ми до неї дійдемо, якщо результат  пошуку в першій підпапці (навіть якщо там None - тобто, не знайдено нічого) зразу ж повертається?

Подякували: quez, Q-bart2

8

Re: Рекурсія

quez написав:

Тут не завадив би пруф про вигідність.

В мене був тестовий проект з подібними завданнями. З аналізом швидкодії, використанням пам'яті і т.д.
Від замовника завдання перевіряли досвідчені програмісти. У листі відгуку був детальний аналіз роботи кожного з групи з коментарями до коду.

9

Re: Рекурсія

Q-bart написав:

Та код не працює... Або я не розумію про рекурсію і що не вистачає в коді або неправильний алгоритм..

У вас трішки-трішки неправильно. Ось робочий варіант:

filesystem = ['C:', ['bin', 'sh', 'ls', 'cd'], ['home', ['sergius', 'secretfile', 'tempfile']], 'tempfile']

def file_search(folder, filename):
    result = []
    for item in folder:
        if isinstance(item, list):
            item[0] = '%s/%s' % (folder[0], item[0])
            res = file_search(item, filename)
            if res:
                result.extend(res)
        elif item == filename:
            result.append('%s/%s' % (folder[0], item))
    return result

print file_search(filesystem, 'tempfile')

Результат:

Прихований текст

['C:/home/sergius/tempfile', 'C:/tempfile']

Подякували: Q-bart1

10

Re: Рекурсія

Master_Sergius написав:
Q-bart написав:

Та код не працює... Або я не розумію про рекурсію і що не вистачає в коді або неправильний алгоритм..

У вас трішки-трішки неправильно. Ось робочий варіант:

filesystem = ['C:', ['bin', 'sh', 'ls', 'cd'], ['home', ['sergius', 'secretfile', 'tempfile']], 'tempfile']

def file_search(folder, filename):
    result = []
    for item in folder:
        if isinstance(item, list):
            item[0] = '%s/%s' % (folder[0], item[0])
            res = file_search(item, filename)
            if res:
                result.extend(res)
        elif item == filename:
            result.append('%s/%s' % (folder[0], item))
    return result

print file_search(filesystem, 'tempfile')

Результат:

Прихований текст

['C:/home/sergius/tempfile', 'C:/tempfile']

Дякую.., що присвятили свій час...

11

Re: Рекурсія

P.Y. написав:
code
def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            return  way_to_file + '/' + filename
        elif type(i) == list :
            found_file=file_search(i, filename)
            if found_file!=None:
                return way_to_file + '/' + found_file

А як ще зробити щоб якщо нема файлу виводило 'False', зараз виводить None..

def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            return  way_to_file + '/' + filename
        elif type(i) == list :
            found_file=file_search(i, filename)
            if found_file!=None:
                return way_to_file + '/' + found_file
    if way_to_file ==     folder[0]:
        return 'False'

Так всюди повертає фолс...

def file_search(folder, filename):
    way_to_file = folder[0]
    for i in folder :
        if i == filename:
            return  way_to_file + '/' + filename
        elif type(i) == list :
            found_file=file_search(i, filename)
            if found_file!=None:
                return way_to_file + '/' + found_file
            if found_fil == None:
                return 'False'

А так - помилка.. Ох та рекурсія..

12 Востаннє редагувалося P.Y. (23.02.2015 23:19:58)

Re: Рекурсія

А як ще зробити щоб якщо нема файлу виводило 'False', зараз виводить None..

Як варіант, можна зробити функцію-обгортку, що викликатиме описано вище функцію, яка повертає None, перевірятиме результат і замінюватиме його на False, якщо там None. Що, втім, на практиці інколи необов'яково, враховуючи, що і False, і None обробляються пітоном як хибність (хоча й None!=False).

Подякували: Q-bart1

13

Re: Рекурсія

def file_search(folder, filename):
    # якщо поточний файл або папка є шуканим, повертаємо його назву
    if folder == filename:
        return filename
    # інакше
    else:
        # перевіряємо, це файл або папка
        if isinstance(folder, list):
            # назва папки зберігається в 0-му елементі, тож треба його перевірити
            # якщо це те, що ми шукаємо, повернути назву
            if folder[0] == filename:
                return filename
            # інакше перебираємо весь вміст папки, тепер ігноруючи 0-й елемент
            for i in folder[1:]:
                # для кожного елементу рекурсивно запускаємо цю ж функцію
                path = file_search(i, filename)
                # якщо повернено рядок, отже десь в цьому напрямі було знайдено шуканий файл/папку
                if isinstance(path, str):
                    # дописуємо в початок шляху ім'я поточної папки і повертаємо "на рівень вище"
                    return folder[0] + '/' + path
                # інакше було повернено False - нічого не знайдено, шукаємо далі
            # якщо цикл пройдено і ми досі не вийшли з функції, значить нічого не знайдено, повертаємо False
            return False
        # якщо файл - далі в цьому напрямі шукати нема що, повертаємо False
        else:
            return False
Подякували: 0xDADA11C7, Q-bart2