Рекурсия

[alekopoko]

#include<stdio.h>
void gg(int a,int b)
{ int i=0;
if(a==20)
return;
printf("%d\n",a);
printf("%d\n",b);
gg(a+1,b-1);
gg(a+1,b);
}
void main()
{
gg(16,10);

}

Объясните пожалуйста что делает return ,когда if true что куда возвращается и что потом вызывается - я запутался
до return все понятно - рекурсивный вызов gg(a+1,b-1); до тех пор пока a!=20
т.е. передаем функции gg: 16 и 10 - консоль выводит 17 и 9 ; 18 и 8; 19 и 7 а ДАЛЬШЕ что консоль выводит и почему столько много чисел я не понял
объясните пожалуйста

[Stilet]

Когда а==20 рекурсия прерывается. Происходит каскадный (так сказать) выход из всех процедур, которые были до него вызваны. Т.е. 4 раза процедура выполнится, но каждое выполнение как-бы будет ждать пока наступит условие выхода.
Представь себе строй, который сержант пересчитывает - каждый следующий отзывается, но перекличка закончится только на последнем и строй может разойтись только в этом случае. Причем расходятся по очереди начиная с последнего.
Так и тут - самый первый вызов gg(); будет ждать пока все остальные отработают, и только потом выйдет сам.

[rrrFer]

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

незнаю что у тебя в голове, но пример адский xD

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

А
f()
B

то выполняется выражение А, потом вызов функции, а после этого управление передается команде B.

Вот так и в твоем случае:

printf("%d\n",b);
gg(a+1,b-1);
gg(a+1,b);

после того, как отработает первая функция вызывается вторая, и обе они рекурсивные, поэтому так много цифр.

[alekopoko]

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

16
10
17
9
18
8
19
7
19
8
18
9
19
8
19
9
17
10
18
9
19
8
19
9
18
10
19
9
19 - последний вызов gg(a+1,b)
10 - последний вызов gg(a+1,b)

это же последний вызов,почему он вышел не первым а последнем,почему не по принципу стека - "последним пришел - первым вышел"

рекурсивный вызов gg(a+1,b-1);

16
10
17
9
18
8
19
7

потом должен идти рекурсивный вызов gg(a+1,b);

17
10
18
10
19
10

но консоль вывела больше значений...намного больше

[Stilet]

незнаю что у тебя в голове, но пример адский xD

Спокуха, все тараканы на своих постах ))
Нопасаранчег.

alekopoko

Давай ка задачу в студию.

[alekopoko]

в кернигане есть код быстрой сортировки(Ч.А.Р. Хоар) и я не могу его разобрать что там и как в нем происходит
тема Рекурсия.
там вызов функции в ней двойной вызов этой же функции и еще в if есть return
и я попробовал написать похожий код только попроще...все равно не понял что происходит после того как в return попал.Еще сильней запутался)

с помощью f10 и точки останова в функции все равно не могу до конца разобраться - все равно нить логики у меня теряется после попадания в return
что возвращается и что потом вызывается я не могу понять

[alekopoko]

#include<stdio.h>
void swap(int v[],int i,int j);
void qsort(int v[],int left,int right)
{
	int i,last;
	if(left>=right)
		return;
	swap(v,left,(left+right)/2);
	last=left;
	for(i=left+1;i<=right;i++)
		if(v[i]<v[left])
			swap(v,++last,i);
	swap(v,left,last);
	qsort(v,left,last-1);
	qsort(v,last+1,right);
}
void swap(int v[],int i,int j)
{
	int temp;
	temp=v[i];
	v[i]=v[j];
	v[j]=temp;
}
void main()
{
	int a[13]={34,52,18,35,21,16,11,22,45,3,67,8,1};
	qsort(a,0,12);
	for(int i=0;i<=12;i++)
	printf("%d ,",a[i]);
}

после return я понимаю что в си я идиот
qsort(v,left,last-1);
qsort(v,last+1,right);
и этот двойной вызов мне уже снится

[Stilet]

А-а-а кажись понял. По-моему там массив делится пополам. Каждые половинки сортируются отдельно, опять таки делясь пополам пока делить есть что. Прям таки как твои клетки делятся.