C++

Forum

 
any ideas about recursion ?

jayt (78)
I have a test on recursion and I have been studying it.I want to test myself.So can anyone give me any basic program so I can make it or ask me something (only recursion).I will be thankful.

thank you!
Last edited on
helios (17574)
Implement a binary search:
We want to search for 47 in a sorted array with the following values:
|1 1 3 4 7 11 18 29 47 76 123 199 322|
^ < 47
|18 29 47 76 123 199 322|
^ > 47
|18 29 47|
^ < 47
|47|
^ = 47 DONE FOUND

Start over and look for 5:
|1 1 3 4 7 11 18 29 47 76 123 199 322|
^ > 5
|1 1 3 4 7 11|
^ < 5
|7 11|
^ > 5
|7|
^ > 5 DONE NOT FOUND
Last edited on
jayt (78)
ohhh !
Can you give me something without array please.

I can make a program but you will laugh because I will make mistakes.
Last edited on
helios (17574)
Alright, but if you can solve that one, you'll ace the test for sure.

A classic, then. The Fibonacci series:
Fibonacci(1)=1
Fibonacci(i)=Fibonacci(i-1)+Fibonacci(i-2)
Another very common is factorials:
factorial(1)=1
factorial(i)=i*factorial(i-1)
jayt (78)
ok I know the factorial one.

here is the program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include<iostream>
using namespace std;
int fact(int n)
{  if (n==1)
   return 1;
else 
return fact(n-1)*n;
}
int main()
{ int a;
cout<<"enter the number whose factorial you want to know  ";
cin >>a;
cout<<"the answer is "<<fact(a);
return 0;
}


I am very very new to programing languages and c++.
sorry if i made any mistakes.
Thanks helios for the question.
Last edited on
jayt (78)
can you please answer your first question how to sort out from an array how any number.
Last edited on
helios (17574)
1
2
3
4
5
6
7
8
9
10
11
 
//return the index if the value is found, or -1 otherwise
int binary_search(int v*,int start,int end,int value){
	int pivot=start+(end-start+1)/2;
	if (v[pivot]==value)
		return pivot;
	if (start==end)
		return -1;
	if (v[pivot]<value)
		return binary_search(v,pivot+1,end,value);
	return binary_search(v,start,pivot-1,value);
}
writetonsharma (1461)
give a folder path..

print all the folders/subfolders and files inside that folder.. that would be a good recursive problem.
helios (17574)
writeonsharma: Yeah, that's a good problem to solve with recursion. Except you can't do it with the standard library. You have to use system calls or use a third party library.
Last edited on
writetonsharma (1461)
hmmm... yes it will be a good problem...

on linux we can use opendir etc etc..

on windows we can use findfirstfile and findnextfile.
jayt (78)
@ Naveen sharma !!
Can you please tell me the answer of your question !
that will be a help for me for my test.

Thanks
helios (17574)
I don't think you'll understand it, but here's one using the WinAPI:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
template<class dest,class src>
dest *copyString(src *str,long len=0){
	if (!len)
		for (;str[len];len++); //strlen() wouldn't work inside a template function.
	dest *res=new dest[len+1];
	res[len]=0;
	for (long a=0;a<len;a++)
		res[a]=str[a];
	return res;
}

//Looks for str1 in str0 from the back.
template<typename T>
long instrB_template(T *str0,T *str1){
	long len0,len1;
	for (len0=0;str0[len0];len0++); //strlen() wouldn't work inside a template function.
	for (len1=0;str1[len1];len1++);
	str0+=len0-1;
	for (long res=len0-1;res>=0;res--,str0--){
		T *str2=str0;
		T *str3=str1;
		for (;*str3;str2++,str3++){
			if (!*str2)
				return -1;
			if (*str2!=*str3)
				goto instrB_000; //Fuck yeah!
		}
		return res;
instrB_000:;
	}
	return -1;
}

long instrB(wchar_t *str0,wchar_t *str1){
	return instrB_template<wchar_t>(str0,str1);
}

template <typename dst,typename src>
void addStringsInplace_template(dst **str1,src *str2){
	ulong len1=0,len2=0;
	for (;(*str1)[len1];len1++);
	for (;str2[len2];len2++);
	ulong len3=len1+len2;
	dst *res=new dst[len3+1];
	res[len3]=0;
	for (ulong a=0;a<len1;a++)
		res[a]=(*str1)[a];
	for (ulong a=0;a<len2;a++)
		res[a+len1]=str2[a];
	delete[] *str1;
	*str1=res;
}

void addStringsInplace(wchar_t **str1,wchar_t *str2){
	addStringsInplace_template<wchar_t,wchar_t>(str1,str2);
}

void addStringsInplace(wchar_t **str1,char *str2){
	addStringsInplace_template<wchar_t,char>(str1,str2);
}

void addStringsInplace(char **str1,wchar_t *str2){
	addStringsInplace_template<char,wchar_t>(str1,str2);
}

void addStringsInplace(char **str1,char *str2){
	addStringsInplace_template<char,char>(str1,str2);
}

/*
behavior:
	xx1b: all files
	x1xb: all directories
	1xxb: recursive
*/
std::vector<wchar_t *> *find(wchar_t *name,char behavior=5){
	WIN32_FIND_DATA ffd;
	std::vector<wchar_t *> *res=new std::vector<wchar_t *>;
	HANDLE hFind = FindFirstFile(name, &ffd);
	if (!hFind)
		return res;
	wchar_t *currentPath,*currentPattern;
	{
		wchar_t *temp=copyString<wchar_t>(name);
		for (wchar_t *a=temp;*a;a++)
			if (*a=='\\')
				*a='/';
		long p=instrB(temp,L"/");
		if (p<0){
			p=0;
			currentPath=copyString<wchar_t>("./");
		}else{
			p++;
			currentPath=copyString<wchar_t>(temp,p);
		}
		delete[] temp;
		currentPattern=copyString<wchar_t>(name+p);
	}
	do{
		if (!wcscmp(L".",ffd.cFileName) || !wcscmp(L"..",ffd.cFileName))
			continue;
		if (!(ffd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)){
			if ((behavior&1)==1){
				wchar_t *temp=copyString<wchar_t>(currentPath);
				addStringsInplace(&temp,ffd.cFileName);
				res->push_back(temp);
			}
		}else{
			wchar_t *temp=copyString<wchar_t>(currentPath);
			addStringsInplace(&temp,ffd.cFileName);
			addStringsInplace(&temp,"/");
			if ((behavior&2)==2)
				res->push_back(temp);
			if ((behavior&4)==4){
				wchar_t *temp2=copyString<wchar_t>(temp);
				addStringsInplace(&temp2,currentPattern);
				std::vector<wchar_t *> *v=find(temp2,behavior);
				delete[] temp2;
				res->insert(res->end(),v->begin(),v->end());
				delete v;
			}
		}
	}while (FindNextFile(hFind, &ffd));
	FindClose(hFind);
	delete[] currentPath;
	delete[] currentPattern;
	return res;
}

I think I had one using Boost, but I don't know where it is.

EDIT: Looking back, it would have been more understandable with std::wstring. Oh, well.
Last edited on
Mythios (1058)
Create the towers of hanoi :)
jayt (78)
Can someone give me a small example
like printing the numbers 15 , 12, 9, 6, 3 on the screen
?
Joe101 (33)
a nice recursion example--not as challenging as the binary search involves pascal's triangle: http://www.mathwarehouse.com/algebra/polynomial/pascals-triangle.php

here's some code for it (this is just the C++ version of some of my old java code )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int getPascalsTerm(int degree,int term) {
	 if(degree <= 1)
		return 1;
	else if(term  == degree || term == 0)
		return 1;
	else
		return getPascalsTerm(degree-1, term-1) +getPascalsTerm(degree-1, term);

	}

int main()
{

int degr= 4;
	for(int i = 0 ; i <= degr ; i++)
        cout<< getPascalsTerm(degr, i) << "  " ;


    return 0;
}


it's nice to be able to contribute to this forum for once
Topic archived. No new replies allowed.