Прежде чем войти, подумай - а нужен ли ты там? Зачем тебе это, если ты не знаешь, как пишется функция? Или препод злой не хочет экзамен ставить?

да надо вот делать, а оно в рекурсии должно еще массив заполнять неизвестно сколько раз, т.е. динамически объявить массив неполучится... :(

Либо передавай счетчик как параметр, либо заведи глобальную переменную.
Лучше первое.

void func (int counter)
{
  if (!counter) return;
  func(--counter); 
}

А лучше так:

void func(void) { char *xz; xz=(char *)malloc(1000); func(); }

(:-0

Рекурсия это самоцель?? Описал бы лучше задачу полностью, может есть более красивое решение. Все таки рекурсия - это зло.

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

void func(){
static int count = 0;
if(++count < 100) func();
}

>Рекурсия это самоцель?? Описал бы лучше задачу полностью, может есть более красивое решение. Все таки рекурсия - это зло.

Скажи это скимерам и лиспунам... Заклюют!

ским это кто ? просветите ;)

Scheme

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

Ви таки будете смеяцца, но в C она тоже часто будет наиболее эффективным решением. KIV просто очень сильно малограмотный...

Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.

А как можно программно размер стека ограничить? Да и для этого есть более простые способы:
sscanf("","%d%d%d"); - например...

> Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.

рекурсивный вызов не обязательно увеличивает использование стэка ..

простно нужно корректно определять termination conditions ..

> Рекурсия это самоцель?? Описал бы лучше задачу полностью, может есть более красивое решение. Все таки рекурсия - это зло.

это ты прикололся? в чем конкретно зло рекурсии?

BTW: ты вообще понимаешь рекурсию то?

>С какой это радости рекурсия - зло, если даже тупой gcc умеет хвостовую рекурсию разворачивать в код более эффективный, чем цикл?

И во что же тупой gcc разворачивает хвостовую рекурсию, уважаемый грамотей??

Разворачивает - стопудово, правда для этого кажется нужно сказать -O3

>это ты прикололся? в чем конкретно зло рекурсии?

Например в читабельности и опасной работе со стеком. Хотелось бы услышать в чем преимущества рекурсии??

>BTW: ты вообще понимаешь рекурсию то? Да вроде как. А ты то хоть понял что это за слово "рекурсия" и о чем топик??

А что самому развернуть религия не позволяет, как Moridinу? Или мозг не до конца осознал что такое рекурсия и как и зачем с ней бороться, как в случае lg?

Тебе уже объясняли, что ЭФФЕКТИВНЕЕ, чем ручной вариант. Ты что, не догоняешь?!?

А слабо самому посмотреть? Hint: рекурсивная запись даёт больше простора для оптимизации.

Проверять лучше всего на функции Аккермана (хотя, ты вряд ли знаешь, что это такое). Там разница особо заметна.

>Ви таки будете смеяцца, но в C она тоже часто будет наиболее эффективным решением. KIV просто очень сильно малограмотный...

Ми посмиялись увожаимый. Можно паhу примеров когда "рекурсия является наиболее эффективным решением" для С например? С обоснованием критерия эффективности.

ЗЫ. Манеры вашего общения оставляют желать лучшего, а еще претендуете на что то, смешно :)

Ты с функцией Аккермана уже разобрался, ламер?

P.S. http://home.in.tum.de/~baueran/thesis/

P.P.S. Большинство хитрих случаев, когда используется рекурсия, вообще нельзя привести к нерекуррентному виду. Попробуй это проделать для хотя бы самого простенького recursive descendant parser. Ну да откуда тебе это знать, ты сложнее "hello, world" никогда ничего не писал..

кто говорит про эффективность то .. рекурсия в первую очередь значительно упрощает код, и является мощнейшим средством для описания fuzzy моделей

что же касается эффективности, так хвостовая рекурсия более и равно эффективна нежели соответсвующий луп, т/к _любой_ луп это неявная рекурсия (теорема?) - это применимо к любому ЯП

как раз правило 'всегда избегай рекурсию' - зло, а этим правилом видимо KIV и придерживается .. мне тебя жаль

>Ты с функцией Аккермана уже разобрался, ламер?

Нашел блин пример, функцию Аккермана. Ты мне еще про ханойскую башню расскажи:)

Нисходящий синтаксический анализатор остался далеко в прошлом, на 3 курсе. Без рекурсии прекрасно обошелся, ибо есть мозги. Завидуй, пыонер :) Кстати "hello, world" пишется С большой буквы и с восклицательным знаком не конце, ламер :)

lg, не строй из себя ламера. Ты говоришь что рекурсия эффективнее, только ни ты ни ламер выскочка-грамотей, не привели критериев эффективности. И вообще разберитесь с логикой высказываний: если луп - простейший вид рекурсии то он рекурсия :) Так что эффективнее луп или рекурсия?

ЗЫ. Вообще рекурсия (математически) определяется в функциональном вычислений и неразрывно связана с понятием функция. Дальше думай. ЗЫЫ. lg мне тебя тоже жаль так тебя к концу дня запарило, что так гнать начал, я удивляюсь :)

>> что же касается эффективности, так хвостовая рекурсия более и равно эффективна нежели соответсвующий луп, т/к _любой_ луп это неявная рекурсия (теорема?) - это применимо к любому ЯП

> lg, не строй из себя ламера. Ты говоришь что рекурсия эффективнее, только ни ты ни ламер выскочка-грамотей, не привели критериев эффективности. И вообще разберитесь с логикой высказываний: если луп - простейший вид рекурсии то он рекурсия :) Так что эффективнее луп или рекурсия?

перечитай еще раз мою фразу если не понял, но на всякий случай разьясню.

луп - это простейшее использование рекурсии, то есть рекурсия является базисом, луп может добавлять что-то, но убавить из базиса никак не сможет (на то он и базис) - поэтому рекурсия более или равно еффективна любого лупа > ЗЫ. Вообще рекурсия (математически) определяется в функциональном вычислений и неразрывно связана с понятием функция. Дальше думай.

так и есть, но ты забываешь про один момент, чтобы добраться до n-го шага рекурсии не обязательно применять функцию n раз (если ты можешь доказать что состояние модели будет идентичным тому что после n-го применения функции)

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

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

Ты идиот. Сравни код, который генерит gcc для цикла и для рекурсии - первый часто менее эффективный.

А кстати, интересно:
int fakr(int i){return (i==1)? 1: i*fak(i-1);}

int fakl(int i){int acc=1; while(i != 1) acc*=i--; return acc;}

bash-2.05b$ gcc -S -o test.as test.c -O3 -foptimize-sibling-calls
bash-2.05b$ cat test.as
        .file   "test.c"
        .text
        .align 2
        .p2align 2,,3
.globl fakr
        .type   fakr,@function
fakr:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        pushl   %eax
        movl    8(%ebp), %ebx
        cmpl    $1, %ebx
        je      .L2
        subl    $12, %esp
        leal    -1(%ebx), %edx
        pushl   %edx
        call    fak
        imull   %ebx, %eax
        addl    $16, %esp
.L3:
        movl    -4(%ebp), %ebx
        leave
        ret
        .p2align 2,,3
.L2:
        movl    $1, %eax
        jmp     .L3
.Lfe1:
        .size   fakr,.Lfe1-fakr
        .align 2
        .p2align 2,,3
.globl fakl
        .type   fakl,@function
fakl:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %edx
        cmpl    $1, %edx
        movl    $1, %eax
        je      .L10
        .p2align 2,,3
.L8:
        imull   %edx, %eax
        decl    %edx
        cmpl    $1, %edx
        jne     .L8
.L10:
        leave
        ret
.Lfe2:
        .size   fakl,.Lfe2-fakl
        .ident  "GCC: (GNU) 3.2 20020903 (Red Hat Linux 8.0 3.2-7)"

Чисто зрительно итерационная версия выглядит проще...

>int fakr(int i){return (i==1)? 1: i*fak(i-1);}

Замени на (хвостовая рекурсия, если я правильно понимаю суть):

int fakr0(int i, int res) { return i == 0 ? res : fakr0(i-1, i*res);}
int fakr(int i) { fakr0(i, 1); }

fakr опущено, ее gcc заинлайнил. Как говорится, найди десять отличий :)

_fakr0:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    .p2align 4,,15
L19:
    testl   %edx, %edx
    je  L18
    imull   %edx, %eax
    decl    %edx
    jmp L19
L18:
    popl    %ebp
    ret

2 KIV & Moridin:

Как бабки базарные... Что, никак нельзя без ругани обойтись?

2lg

Такой тезис:

Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.

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

Если функции синлайнить (кстати, gcc не умеет инлайнить рекурсивные функции, по крайней мере мой gcc 3.2), то, конечно, разницы вообще не будет.

Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.

Ещё один не догнал.

Не ТАК ЖЕ будет, а ЭФФЕКТИВНЕЕ. Потому как больше возможностей для оптимизации.

Да, ещё: прикол N2. На современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода! Артефакт предсказателя ветвлений, как правило...

Moridin (19.01.2005 19:36:36):

> Потому как больше возможностей для оптимизации.

Я же написАл, что мы все соптимизировали!

Moridin (19.01.2005 19:37:54):

> На современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода! Артефакт предсказателя ветвлений, как правило...

Голословно.

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

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

Ну возьми, соптимизируй Аккермана руками (на Цэ, естественно) лучше, чем gcc рекурсивную версию.

Я же конкретный пример привожу!

Moridin (19.01.2005 19:53:54):

> ...соптимизируй Аккермана руками ... Я же конкретный пример привожу!

Где "конкретный пример"? Я могу Аккермана по-разному вычислять, целые тома про нее написаны!

Покажи мне работающую использующую рекурсию программу на Це, которую невозможно переписать с без рекурсии так, чтобы она работала с такой же или лучшей эффективностью.

> Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.

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

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

> Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.

В теории рекурсия всегда не медленнее лупинга, но на практике пока все еще это не так хотя приближается ...

кстати нашел вот показательную выдержку из AoA(Art of Assembly Language) [надеюсь никто не ставит под сомнение ее авторитетность? ;)]

...there are only a few recursive algorithms that you cannot implement in an iterative fashion. However, many recursively implemented algorithms are more efficient than their iterative counterparts and most of the time the recursive form of the algorithm is much easier to understand...

2lg :

А что мы понимаем под рекурсией? Можно определение?

Программа в конце концов транслруется в коды, и пара call/return -- всего лишь longjump'ы со спасением/чтением адреса возврата. Железяка по природе своей итеративна, она не знает, что такое функция. Если я формально напишу блок-схему странслированной в машинные коды программы, то я не получу ничего, кроме goto в некоторых ветвях.

хорошо - рекурсия это метод создания модели используя рекурсивные функции. Рекурсивная функция это функция которая может явно или не явно использовать саму себя для вычисления результата

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

так же при рекурсии у тебя не обязательно будет расти стек ..

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

>На современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода! Артефакт предсказателя ветвлений, как правило...

Дальше с тобой говорить ИМХО не о чем. _Современные_ процессоры используют спекулятивные(предикативные) методы предсказания переходов, Если поинтересуешься то узнаешь что в этом случае разницы между вызовом функции и безусловным переходом не будет. Учите матчасть, знаток Аккермана :)

>Как бабки базарные... Что, никак нельзя без ругани обойтись?

Прошу прощения у общественности. Но трудно общаться с Moridin.

To Die-Hard Ты сам скоро это поймешь!

А можно поподробнее о "...на современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода!". Примеры в РЕАЛЬНЫХ ISA можно? Это абсолютно голословное утверждение, и если Вы не приведёте примеры,то это лишь докажет тот факт, что ТЫ ЛАМЕР!

Уважаемый lg простите что заподозрил вса в том что вы претваряетесь ламером. Теперь я понял - вы не претворяетесь.

Ваша несостоятельность в подтверждении вашиж же слов это подтверждает. Следующие ваши безосновательные фразы размещю в разделе юмор :) :

>1. луп - это простейшее использование рекурсии, то есть рекурсия является базисом

А не наоборот?

>2. так же при рекурсии у тебя не обязательно будет расти стек ..

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

>3. рекурсия .... это еффективное средство для упрощения кода, и простроения алгоритмов.

Не слишком все таки замашки?

> А можно поподробнее о "...на современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода!". Примеры в РЕАЛЬНЫХ ISA можно?

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

иди в школу или садик, если тебе не больше 10 лет, можешь попробовать поступить ко мне, если сможешь конечно ..

>>1. луп - это простейшее использование рекурсии

>А не наоборот? ... Не слишком все таки замашки?

Доказываю:

Любой "цикл" можно заменить идентичной по сложности описания рекурсивной ф-ей, тупо заменив все "continue" на "return F(новые значения переменных цикла)". Обратное, очевидно, неверно. Следовательно рекурсивный метод описания алгоритмов есть более эффективным/мощным/кошерным/...

Ой какое рубилово.....:-)

Я человек тут новый и вообще малограмотный... по моему таки есть ситуации где рекурсия гораздо удобнее (напр обработка массивов ПРОИЗВОЛЬНОЙ размерности), всякий анализ, и еще куча примеров... да, можно это все сделать и без, но непонятно зачем? Мне казалось что хороший программист это тот кто владеет широким арсеналом приемов и умеет их примеянть грамотно, ... а не тот кто виртуозно владеет одним приемом и лепит им все подряд. "Если бы у рыб была шерсть..."(с) :_)

Про эффективность - а что, что то более эффективное чем рекурсивные темплейты уже появилось? Я просто не в курсе, не слежу за новациями.. Но, посзволю напомнить, отлаживать эти самые темплейты жуткий геморрой.

>>2. так же при рекурсии у тебя не обязательно будет расти стек ..

>Можно было поподробнее в этом месте, если уж действительно желаете что то донести

Читать про хвостовую рекурсию. Например, для корректной реализации Scheme стек в случае хвостовой рекурсии _обязательно_ _не_ будет расти (не совсем корректное утверждение, но фактически это так). Это просто требование к имплементации.

>теоретически это конечно же возможно (про практику ничего не могу сказать)

А чего тогда втираешь почтенной публике?

>При неизбежном росте длины конвейра,

Почему неизбежном то? Например процессоры с архитектурой VLIW (Crusoe и Efficeon например) ничего никуда не ростят :).

>увеличивается пенальти(возможно даже не линейно, а круче) за misprediction, в итоге может возникать ситуация что глупый branch predictor будет ошибаться и ты получишь пенальти которое по времени будет больше чем вызов функции

missprediction чего? безусловного перехода? Тут с условными то проблем не возникает, посмотри спецификацию EPIC например что-ли, ради разнообразия, если до этого методик предикативного исполнения команд не встречал.