JavaRush /Курсы /Harvard CS50 /Рекурсия (заметки к видеолекции)

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

Harvard CS50

4 уровень , 2 лекция

Открыта

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

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

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

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

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

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

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

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

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

Когда выполняется условие выхода из рекурсии, функция завершается без рекурсивного вызова.
Возьмем функцию 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!” и закончит свою работу.

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

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

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

То есть

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

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

Теперь напишем код для подсчёта факториала. Создадим функцию 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.

На первых этапах знакомства с рекурсией могут быть проблемы с пониманием этого алгоритма. Важно понять, что она как бы «раскручивается» до базиса рекурсии, и затем вновь «закручивается». То есть, если нам нужно определить 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

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (13)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Anonymous #3598185 Уровень 2

12 июля 2025

бинарный:


include <stdio.h>
#include <stdbool.h>

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

int size;

void main(void) {
    int array[] = {2, 3, 5, 6, 7, 9, 12, 14, 23, 67, 78};
    int n;

    printf("size:");
    scanf("%i", &size);
    printf("n:");
    scanf("%i", &n);

    if(search(n, array, 0, size-1)) {
        printf("true");
    }
    else {
        printf("false");
    }
}

bool search(int n, int array[], int lower, int upper) {
    if (array[lower] > n || array[upper] < n) {
        return false;
    }
    if (array[lower] == n || array[upper] == n ) {
        return true;
    }
    if (upper - lower == 1) {
        return false;
    }

    int middle;
    int middle_index;

    if ((upper+lower) % 2 != 0) {
        middle_index = (upper+lower) / 2;
    }
    else {
        middle_index = ((upper+lower) + 1) / 2;
    }
    middle = array[middle_index-1];

    if (n == middle) {
        return true;
    }
    else if (n > middle) {
        return search(n, array, middle_index, size-1);
    }
    else if (n < middle) {
        return search(n, array, 0, middle_index);
    }
}

Global Dev Уровень 1

1 февраля 2025

Sigma:


#include<stdio.h>
#include<cs50.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

int sigma_recursion(int n);
int sigma_for(int n);

int main(void)
{
    int mode = get_int("Select mode(1 - recursion, 2 - for): ");
    int n = get_int("--Sigma--\n\nInput: ");
    if(mode == 1)
    {
        printf("%i\n", sigma_recursion(n));
    }
    if(mode == 2)
    {
        printf("%i\n", sigma_for(n));
    }
    else
    {
        return 1;
    }
}

int sigma_recursion(int n)
{
    if(n == 1)
    {
        return 1;
    }
    else
    {
        return n + sigma_recursion(n-1);
    }
}

int sigma_for(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        sum += n-i;
    }
    return sum;
}

FeatHonnar Уровень 16

3 октября 2022

Вот мои версии функций и коды для проверки вместе с ними: Сигма


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

int sigma (int n)
{
    if (n < 1) {
        return 0;
    }
    return n + sigma(n - 1);
}
int main()
{
    int num = get_int("");
    num = sigma(num);
    printf("%i", num);
}

Бинарный поиск:


#include <cs50.h>
#include <stdio.h>
//Непосредственно binsearch
bool search(int n, int array[], int start, int end)
{
    while (start <= end) {
        int mid = (start + end) / 2;
        if (array[mid] == n) {
            return 1;
        }
        if (array[mid] < n) {
            start = mid + 1;
            search(n, array, start, end);
        }
        if (array[mid] > n) {
            end = mid - 1;
            search(n, array, start, end);
        }
    }
    return 0;
}
//Код для проверки
int main()
{
    int arrx[] = {1, 3, 5, 7, 9, 11};
    int arry[] = {2, 4, 6, 8, 10, 12};
    int key = get_int("your number:\n"), change = get_int("your mode:\n");
    if (change % 2 == 0) {
        if (search(key, arry, 0, 5)) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    else {
        if (search(key, arrx, 0, 5)) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
}

Евгений Уровень 1

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;
}

FeatHonnar Уровень 16

3 октября 2022

Синтаксис покинул чат)

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

9 ноября 2020


Collections.sort(sort);
        System.out.println("Введите искомое значение:");
        boolean m2 = true;
        int number=0;
        while (m2){
        try {
            while (true){
                number = Integer.parseInt(reader.readLine());
                m2 = false;
                break;
            }
        }
        catch (Exception e){
            System.out.println("Введите целое число:");

        }}

        Integer result = search(number, sort, 0, sort.size() -1);
        if (result == null) System.out.println("Искомого числа нет в списке!");
        else {
            for (Map.Entry<Integer, Integer> pair : numbers.entrySet()){
                int key = pair.getKey()+1;
                int volume = pair.getValue();
                if (volume == result) System.out.println("Искомое число было введено в " + key + " строке");

            }
        }

    }
    public static int findMidpoint(int left, int right){
        int midpoint;
        if ((left + right)%2 == 0) midpoint=(left+right)/2;
        else midpoint = (left + right)/2 +1;
        return midpoint;
    }
    public static Integer search(int number, ArrayList<Integer> list, int left, int right){
        if (number < list.get(left) || number > list.get(right)) return null;
        else{
            int midpoint;
            midpoint = findMidpoint(left, right);
            if (list.get(midpoint) < number)  {

                return search(number, list, midpoint +1, right);
            }

            else if (list.get(midpoint) > number)  {

                return search(number, list, left, midpoint -1);
            }
            else  return number;
        }

    }
}

Александр Уровень 19

24 марта 2024

Надеюсь, скоро начну понимать такое =)

pro100Lesha Уровень 31

8 ноября 2020

/* Комментарий удален */

Челмедведосвин Уровень 1

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;
    }
}

Maria Gregory Уровень 1

8 марта 2019

Очевидно, коду


 else return false;

в линиях 70-71 никогда не суждено сбыться.

Челмедведосвин Уровень 1

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".