Хороший банк рекурсивных решений в C/С++/Java/С#

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

Он изучил проблему теоретически, но испытывает проблемы с пониманием того, как реально решать проблемы рекурсии. Знаете ли вы хороший источник проблем рекурсивных задач (желательно на C, но также можете быть на языке C-стиля), доступных в сети?

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

Ответ 1

Эта статья объясняет рекурсию и содержит некоторые простые примеры C для перемещения связанного списка и двоичного дерева

Ответ 2

Один из лучших способов изучения рекурсии - получить некоторый опыт в функциональном языке программирования, таком как Haskell или Lisp или Scheme.

Таким образом, поиск рекурсивных проблем может быть сведен к поиску некоторых проблем и ответов, связанных с функциональными языками программирования. Вот пример 99 Lisp проблемы.

Для изучения схемы или Lisp требуется всего 5 минут, чтобы вы могли сразу начать использовать примеры, которые вы указали завтра.

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

Ключевые понятия, относящиеся к рекурсии:

С рекурсией вам не нужно знать, как решить проблему. Вам просто нужно знать 2 вещи. 1) как решить наименьший экземпляр проблемы и 2) как разбить ее на более мелкие части.

Эквивалентно, вам просто нужно иметь в виду, что вам нужно: 1) базовый случай и 2) рекурсивный случай.

Базовый регистр обрабатывает 1 единственный экземпляр того, что вы хотите сделать с наименьшим входом.

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

Пример:

//1+...+n = n*n(+1)/2 = sumAll(n):

int sumAll(int x)
{
  if(x == 0) //base case
    return 0; 
  else
    return sumAll(x-1) + x; //recursive case
}

Важно понимать, что базовый случай не сложно понять. Он просто должен существовать. Вот эквивалентное решение для x > 0:

//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
  if(x == 1) //base case
    return 1; 
  else
    return sumAll(x-1) + x; //recursive case
}

Ответ 3

Это будет звучать как очень слабый ответ, но рекурсия - это парадигма, которую часто очень трудно понять в первом для новичков. Для вашего друга потребуется более чем на один день медитация, чтобы ваш друг твердо понял концепцию.

Возможно, вам захочется, чтобы он просмотрел Project Euler для потенциального направления изучения.

Ответ 4

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

sumAll [] = 0
sumAll (x:xs) = x + sumAll xs

Чтобы понять это, вам действительно нужно знать, что

[] представляет пустой список,
(x: xs) разбивает список на голову (x) и хвост (xs)

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

Ответ 5

В языке c/С++ функция может вызывать себя, и этот случай называется рекурсией. В основном рекурсия имеет два случая:

Базовый регистр.
рекурсивный случай.

и у нас есть некоторые рекурсивные категории, такие как...

Рекурсия Liner
Двоичная рекурсия
Вложенная рекурсия
Взаимная рекурсия
Рекурсия хвоста

Вот пример, чтобы обсудить рекурсию...

// a recursive program to calculate NcR  //
#include <stdio.h> 
int ncr(int x,int y)
{
    if(y>x)
    {
        printf("!sorry,the operation can't processed.");
        getch();
        exit(1);
    }
    else if(y==0 ||y==x)   //base case
    {
        return(1);
    }
    else
    {
        return(ncr(x-1,y-1)+ncr(x-1,y));  //recursive case
    }
}

Ответ 6

Чтение SICP (структура и интерпретация компьютерных программ)

Ответ 7

#include<iostream>
using namesspace std;
int E(int x);
int main()
{
    int x;
    cout << E(x) << endl;
    return 0;
}

int E(int x)
{
    return x ? (x % 10 + E(x/10)) : 0;
}