написать рекурсивную функцию на Си

[Бумер]

Нужно написать рекурсивную функцию на Си

Найти номер последнего вхождения максимума в последовательность. Последовательность вводится с клавиатуры, длина послдовательности - l

[Форматцевт]

# include    main ()						   /*  вызывающая	 */   {   int x,y,n,t;				  /*  функция		 */	   int ackr(int, int, int);	   scanf("%d %d %d",&n,&x,&y);	   t=ackr(n,x,y);	   printf("%d",t);   }  int smacc( int n,int x )		  /*  вспомогательная  */  {   switch (n)					/*   функция		 */	   {  case 0:  return(x+1);		  case 1:  return (x);		  case 2:  return (0);		  case 3:  return (1);		  default: return (2);		}  }  int ackr( int n, int x, int y)	/*  рекурсивная	  */  {  int z;						 /*  функция		  */	 int smacc( int,int);	 if(n==0 || y==0)  z=smacc(n,x);	 else { z=ackr(n,x,y-1);		/*  рекурсивные	  */			z=ackr(n-1,z,x);  }	 /*  вызовы ackr(...) */	 return z;  }

Бумер: так, а теперь моё мнение, задачи надо делать самому, а то это не учёба получается. ИМХО

Изменено 11 апреля, 2007 пользователем Darhazer

[Бумер]

Согласен, что-то я зачастил...

Я вот непонимаю, зачем рекурсию в этой задаче использовать? Ведь все решается гораздо проще и нагляднее при помощи итерационного цикла!!!

Ведь рекурсия - это не только лишняя нагрузка на мозги программиста и запутанная логика - это же еще время на вызов функций и опасность переполнить стек!!!

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

[Тролль]

Бумер:

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

Ты не знаешь как... А мне так непонятно, что...

Вот последовательность: 2,3,5,1,5,3,0,2,1

В ней 3 максимума, из них два глобальных, номер последнего локального максимума 3 (он третий локальный максимум в последовательности), номер последнего глобального максимума 2 (он второй глобальный максимум в последовательности).

Каким должен быть ответ? Если понимать точно по условию, то "номер последнего вхождения максимума в последовательность" - это 3.

Но мне так кажется, имелось в виду вообще не то, что написано, а просто ваш препод не смог правильно сформулировать задание - имелся в виду индекс элемента последовательности, содержащего последний глобальный максимум. То есть в данном случае 4-й элемент, если нумерацию элементов последовательности вести от нуля, как принято в C, и в этом примере ответ должен быть 4. Или, может, надо считать элементы последовательности от единицы, тогда ответ 5. Так какой ответ правилен?

Я не придираюсь, но при сдаче задания запросто может оказаться, что препод хотел не то, что просил. Вот тогда и доказывай, что верблюд - препод :)

Изменено 11 апреля, 2007 пользователем Тролль

[Бумер]

Тролль: Так это всегда так бывает, но похоже что надо выводить номер 4, считая нумерацию с нуля. Но не суть в этом. Я хочу научиться писать рекурсивные алгоритмы для вот таких задач. Если там вычисление энного члена последовательности Фибоначчи - это по самой природе алгоритм рекурсивный, то зачем его применять в ТАКИХ задачах???

Есть там хоть какая то методология составления рекурсивных алгоритмов в нетривиальных (ну в смысле, если алгоритм от природы не рекурсивный, как в данном случае) зачач???

Вообще надо как бы "зацепить" рекурсию, т.е. понять что она будет делать на каждом шаге. Вот и попробуй, зацепи эту рекурсию в подобных задачах!!!

Вообще правильно я где-то читал про рекурсию: ее полностью характеризует письмо больного врачу в психиатрич. больнице:"Я вам пишу, что я вам пишу, что я вам пишу..." :)

Indomito: Я не понял как работает твоя прога:(. Пока сам не напишешь - наверное не поймешь.

Напишите, если у вас есть адреса хороших сайтов, посвященных составлению рекурсивных алгоритмов.

[Форматцевт]

Бумер: знаешь, просто я в гугле поискал, по названию твоего топика, вот запрос рекурсивная функция на Си и всё там есть, даже описание/пособие как писать рекурсию. :) Гугл рулит и бибикает :(

ЗЫ Да, совсем забыл. Обучение сводится не к простому изучению дисциплин, но и умению пользоваться литературой, справочниками, пособиями и тд. :)

ЗЗЫ Ведь всё уже писано преписанно - осталось только найти.

Изменено 12 апреля, 2007 пользователем Indomito

[Бумер]

Indomito: Ну я яндекс тоже помучал, но только нормального ничего не нашел, всякая туфта - обсуждение на форуме, как сделать очередную прогу:(

Мне надо хорошие линки

[Форматцевт]

Бумер: вот, ещё и тут

Рекурсия:

У попа была собака, он ее любил.

Она съела кусок мяса, он ее убил.

Камнем придавил, и на камне написал :

У попа была собака... :(

[Тролль]

Бумер:

А вообще есть методика для составления рекурсивных функций ... ?

Какая тут методика? Все очень просто: если мы будем знать максимум для первых l-1 элементов, то достаточно будет сравнить этот максимум и последний элемент. А как узнать максимум для l-1 элементов? Да очень просто, если мы знаем максимум для l-2 элементов: сравнить этот максимум и (l-1)-й элемент. И так далее... Вот тебе и рекурсия. Конкретно решение твоей задачи выглядит так

#include <stdio.h>int a[]={2,3,5,1,5,3,0,2,1},l=sizeof(a)/sizeof(int)-1,k=0;int maxi(int l) {if(l>=0 && a[l]>=maxi(l-1)){k=l; return(a[k]);}}int main() {maxi(l); printf("%5d\n",k);getch();}

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

Теперь о рекурсии. Фактически всегда есть два подхода - решение "в лоб" и рекурсия. Но рекурсия становится тем удобнее, чем сложнее задача. Подавляющее большинство сложных задач, типа нахождения оптимальных значений с помощью динамического программирования, решаются только с помощью рекурсии. Или, например, синтаксический разбор - тот же компилятор языка С разбирает твои строки рекурсивно. Да даже пример обычного инженерного калькулятора - гораздо проще написать вычисление арифметических выражений со скобками, если использовать рекурсию.

У тебя тут так называемая простая рекурсия. Но могут быть гораздо более сложные ее виды. Например, косвенная - когда A сводится к B, а B сводится опять к A. А можно и сложнее, ветвящуюся рекурсию: A сводится к B и C, В сводится к A и С, а C сводится к A и B...

Функция Аккермана, программу для вычисления которой привел Indomito - один из самых простых примеров "сложной" рекурсии.

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

Вообще есть методики перевода рекурсивного решения в нерекурсивное, посмотри хотя бы третью ссылку Indomito, там описана соответствующая методика. А обратным переводом практически не занимаются за ненадобностью. Но нерекурсивное решение для не самых примитивных случаев рекурсии, хотя бы типа калькулятора для выражений со скобками, записывается обычно гораздо сложнее рекурсивного.

Переполнение стека и так далее - да, рекурсивные вычисления требуют более сложных компиляторов. Но какое переполнение стека может быть при динамическом выделении памяти? Просто это более высокий уровень требований к компилятору. Когда-то было четкое деление языков: эффективные простые без рекурсии и сверхмощные медленные, основанные на рекурсии (типа Prolog и его потомков). Но сейчас рекурсия реализуется компиляторами гораздо эффективнее.

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

Но Indomito прав - надо учиться не только программировать, но и учиться учиться программировать, то есть самому искать и находить решения новых для тебя задач. И, конечно, решать примеры.

Indomito:

Камнем придавил, и на камне написал :

Это какой-то другой вариант классической рекурсии ;) . В моей рекурсии было:

"И в землю закопал, и надпись написал, что"

Изменено 12 апреля, 2007 пользователем Тролль

[Форматцевт]

Тролль: задавил интеллектом тов. Бумера ....шутка конечно, но

Юмор о рекурсии ;)

- Известное высказывание: Чтобы понять рекурсию, нужно сначала понять рекурсию.

- Рассказ про Йона Тихого о сепульках («Звёздные дневники Йона Тихого»), в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».

- Почти Гамлет - "To define through itself or to not define - here in what a question."

Изменено 12 апреля, 2007 пользователем Indomito