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

#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");
        }
    }
}

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

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("");
      //продолжение ниже

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

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