undefined

Рекурсия (заметки к видеолекции)

Harvard CS50
4 уровень , 2 лекция
Открыта

Рекурсивные структуры данных — это те структуры данных, которые содержат сами себя в собственных определениях. Но сегодня мы сосредоточимся на рекурсивных функциях.

Итак. Практически все функции принимают на вход некоторые данные и возвращают что-то на выходе.

функция

На рисунке параллелепипед — тело функции, то есть набор неких инструкций, которые интерпретируют исходные данные и формируют выходные.

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

рекурсивная функция

Вот, например, эта простейшая функция foo. Она принимает на вход строку, подсчитывает количество символов в ней и выводит на экран это число.

Чтобы посчитать длину строки, функция вызывает другую функцию — strlen.

функция strlen

Данные, которые она генерирует на выходе, нужны, чтобы вывести их на экран с помощью printf.

функция printf

Особенность рекурсивной функции в том, что она вызывает сама себя. Обозначим этот процесс на картинке оранжевой стрелкой. Однако вызов самой себя предполагает ещё один рекурсивный вызов… А затем ещё один, и ещё один!

особенности рекурсивной функции

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

Рекурсия (заметки к видеолекции) - 1

Когда выполняется условие выхода из рекурсии, функция завершается без рекурсивного вызова.
Возьмем функцию hi. Она ничего не возвращает, но принимает на вход целое число n.

void hi(int n)
{
	if (n <= 0)
	{
		printf("Bye!\n");
		return;
	}
	printf("Hi!\n");
	hi(n-1);		
}

Выход из рекурсии идёт первым. Если n <= 0 мы просто выводим «Bye!» и выходим из функции. Для всех других случаев функция будет выводить «Hi!» и делать рекурсивный вызов — то есть ещё один вызов функции hi с уменьшенным на единицу значением n. И так будет продолжаться до тех пор, пока n не станет равно нулю. Тогда функция напишет “Bye!” и закончит свою работу.

Рекурсия (заметки к видеолекции) - 2

Поскольку hi ничего не возвращает, мы можем не писать return явным образом.

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

Факториалом целого положительного числа n называется произведение всех целых положительных чисел, которые меньше или равны n.

Рекурсия (заметки к видеолекции) - 3

То есть

5! = 5*4*3*2*1 = 120
4! = 4*3*2*1 = 24
3! = 3*2*1 = 6 
2! = 2*1 = 2
1! = 1 

И да, по определению, 0! = 1.

Как можно написать функцию, которая рекурсивно подсчитывает факториал числа? Для начала нам нужно определить выход из рекурсии и рекурсивный вызов.

Рекурсивный вызов будет одинаков для всех случаев, кроме выхода. Это значит, нам нужно найти шаблон, который поможет нам решить задачу. На картинке выше видно, что 5! — это 4!*5, 4! — это 3!*4 и так далее, вплоть до 1!, который равен 1.

Таким образом, наш шаблон для нашего рекурсивного вызова:

n! = (n-1)! * n
Рекурсия (заметки к видеолекции) - 4

А наш выход из рекурсии или базис рекурсии будет определение факториала для единицы.

Рекурсия (заметки к видеолекции) - 5

Теперь напишем код для подсчёта факториала. Создадим функцию int factorial (int n). Для выхода из рекурсии нам нужно, чтобы выполнилось условие n == 1. В таком случае мы возвращаем 1. Потом, двигаясь по рекурсивному вызову мы будем возвращать n*factorial(n-1).

int factorial(int n)
{
    // base case
    if (n == 1)
    {
        return 1;
    }

    // recursive case
    return n * factorial(n - 1);
}

Протестируем программу. Попробуем найти 4! Для нашей функции это 4*factorial(3), а factorial(3) = factorial(2)*3, factorial(2) = factorial(1) *2. Ну а factorial(1) в свою очередь равен 1.

Мы получили эту единицу, и теперь последовательно возвращаем 2, 2*3 = 6, 6*4 = 24.

Рекурсия (заметки к видеолекции) - 6

На первых этапах знакомства с рекурсией могут быть проблемы с пониманием этого алгоритма. Важно понять, что она как бы «раскручивается» до базиса рекурсии, и затем вновь «закручивается». То есть, если нам нужно определить 5!, считайте, что 4! у нас уже есть.

Задание

Чтобы убедиться, что вы хорошо поняли рекурсию, попробуйте выполнить следующее задание:

Создать рекурсивную функцию sigma, которая считывает сумму натуральных чисел от 0 до заданного на входе числа n.

int sigma (int n);

В консоли должно отобразиться что-то в этом роде:

jharvard@run.cs50.net (~): ./a.out
Enter a positive integer: 5
15

Ну а если вы чувствуете себя совсем уверенно, попробуйте создать рекурсивную функцию бинарного поиска (помните разорванную Дэвидом книгу?).

Давайте поищем число n в заданном массиве.

bool search(int n, int array[], int lower, int upper);

Она должна возвращать true, если число n найдено, и false, если нет.

jharvard@run.cs50.net (~): ./a.out
> 4
YES
Комментарии (9)
Чтобы просмотреть все комментарии или оставить свой,
перейдите в полную версию
Maks Panteleev 23 уровень, Москва
25 апреля 2021

    static boolean search(int n, int array[], int lower, int upper){
        if (lower > upper) return false;
        int mid = (lower+upper)/2;
        if(n==array[mid]) return true;
        if(n<array[mid]) return search(n,array,lower,mid-1);
        if(n>array[mid]) return search(n,array,mid+1,upper);
        return false;
    }
Евгений 28 уровень, Москва
18 ноября 2020
Бинарный поиск на Си (вроде как Java не изучаем на данном курсе 😀 (посмотрел сообщения ниже) )

#include <cs50.h>
#include <stdio.h>

bool search(int n, int array[], int lower, int upper);

int main(void)
{
    int DIM_ARRAY=8;
    int array[8]={1, 2, 3, 4, 5, 6, 8, 90};
    int find_digit = get_int("Enter digit: ");
    printf("%s\n", search(find_digit,array,0,DIM_ARRAY - 1) ? "YES" : "NO");
}

bool search(int n, int array[], int lower, int upper)
{
    if (lower > upper) return false;
    if (lower==upper) return (n == array[upper]);
    int middle_element = (lower + upper) / 2;
    if (n > array[middle_element]) return search(n, array, middle_element+1, upper);
    if (n < array[middle_element]) return search(n, array, lower, middle_element-1);
    return true;
}
pro100Lesha 31 уровень
9 ноября 2020
Бинарный поиск на Java, в качестве результата возвращает номера строк в которых находилось искомое число.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class b2search {
    public static void main(String[] args) throws Exception {
        System.out.println("Введите массив, каждый элемент с новой строки, для завершения введите пустую строку");
        boolean m = true;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Integer> numbers = new HashMap<Integer, Integer>();
        int index =0;
        while (m){
        try{
            while (true){
            String string = reader.readLine();
            if (string.isEmpty()) {
                m=false;
                break;
            }
            numbers.put(index, Integer.parseInt(string));
            index++;
            }
        }
        catch (Exception e){
            numbers.clear();
            System.out.println("Данные не корректны, введите целые числа, каждое c новой строки");
        }

        }
        ArrayList<Integer> sort = new ArrayList<>();
        System.out.println("Исходные данные:");
        for (Map.Entry<Integer, Integer> pair : numbers.entrySet()){
            int number = pair.getValue();
            sort.add(number);
            System.out.print(number + " ");
        }
        System.out.println("");
      //продолжение ниже
pro100Lesha 31 уровень
8 ноября 2020
/* Комментарий удален */
Челмедведосвин 41 уровень
31 августа 2018
Бинарный поиск

#include <stdio.h>
#include <cs50.h>

bool search(int n, int array[], int lower, int upper);
int findMidpoint(int lower, int upper);

int main(void)
{
    printf("Введите размер массива: ");
    int size = get_int();
    int array[size];
    for (int i=0; i<size; i++)
    {
        printf("Введите %i элемент массива: ", i+1);
        array[i] = get_int();
    }

    printf("Исходный массив: ");
    for (int i=0; i<size; i++)
    printf(" %i", array[i]);
    printf("\n");

    printf("Отсортированный массив:");
    for (int i=0; i < size; i++)
    {
        for (int j=i+1; j < size; j++)
        if (array[i]>array[j])
        {
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
        printf(" %i", array[i]);
    }
    printf("\n");

    printf("Введите искомое значение: ");
    int value = get_int();
    bool result = search(value, array, 0, size-1);
    if (result == true)
    printf("Это число есть\n");
    else
    printf("Этого числа нет\n");
}

int findMidpoint(int lower, int upper)
{
    int midpoint;
    if ((lower + upper)%2 == 0)
    midpoint = (lower + upper)/2;
    else
    midpoint = (lower + upper)/2+1;
    return midpoint;
}

bool search(int n, int array[], int lower, int upper)
{
    if (n > array[upper] || n < array[lower])
    return false;
    else
    {
        int midpoint;
        midpoint = findMidpoint(lower, upper);
        if (array[midpoint] < n)
        return search(n, array, midpoint+1, upper);
        else if (array[midpoint] > n)
        return search(n, array, lower, midpoint - 1);
        else if (array[midpoint] == n)
        return true;
        else
        return false;
    }
}
Челмедведосвин 41 уровень
31 августа 2018
Рекурсивная функция Sigma

#include <stdio.h>
#include <cs50.h>

int sigma(int n);

int main(void)
{
    printf("Введите число: ");
    int a = get_int();
    printf("Результат функции sigma: %i\n", sigma(a));
}
int sigma(int n)
{
    if (n==0)
    return 0;
    return n+sigma(n-1);
}
Maksud 1 уровень, Львов
6 июня 2018
Кажется это ошибка. В функции hi(int n), когда функция вызывается последний раз - hi(0), printf должен быть "Bye", а не "Hi".