any ideas about recursion ?

Apr 28, 2009 at 3:04am
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 Apr 28, 2009 at 3:04am
Apr 28, 2009 at 3:36am
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 Apr 28, 2009 at 3:36am
Apr 28, 2009 at 3:39am
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 Apr 28, 2009 at 3:43am
Apr 28, 2009 at 3:45am
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)
Apr 28, 2009 at 3:51am
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 Apr 28, 2009 at 6:19am
Apr 28, 2009 at 3:54am
can you please answer your first question how to sort out from an array how any number.
Last edited on Apr 28, 2009 at 3:54am
Apr 28, 2009 at 4:11am
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);
}
Apr 28, 2009 at 4:53am
give a folder path..

print all the folders/subfolders and files inside that folder.. that would be a good recursive problem.
Apr 28, 2009 at 11:06am
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 Apr 28, 2009 at 11:07am
Apr 28, 2009 at 1:11pm
hmmm... yes it will be a good problem...

on linux we can use opendir etc etc..

on windows we can use findfirstfile and findnextfile.
Apr 29, 2009 at 3:41am
@ Naveen sharma !!
Can you please tell me the answer of your question !
that will be a help for me for my test.

Thanks
Apr 29, 2009 at 3:59am
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 Apr 29, 2009 at 4:04am
Apr 29, 2009 at 4:07am
Create the towers of hanoi :)
May 11, 2009 at 4:44pm
Can someone give me a small example
like printing the numbers 15 , 12, 9, 6, 3 on the screen
?
May 12, 2009 at 1:51am
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.