CS 32 Lecture 9. Recursion(2), Generic programming
Class Challenge
Write a function that finds and returns the earliest position of a number in a linked list. If the number is not in the list or the list is empty, your function should return -1 to indicate this.int findPos(int *curr, int num)
{
if (!curr)
return -1;
if (curr->val == num)
return 0;
if (findPos(cur->next, num) == -1)
return -1;
else
return 1+findPos(cur->next, num);
}
Memory usage!
Be careful!! Recursion can be a pig when it comes to memory usage!
Never let your recursive calls get too deep!
Binary Search
Goal: Search a sorted array of data for a particular item
Idea: Use recursion and a divide-and-conquer approach!// pseudocode
Search(sortedWordList, findWord)
{
if no word in the list
not found
if findWord == middle word
found
if findWord < middle word
Search(first half of sortedWordList);
else
Search(second half of sortedWordList);
}
int BS(string A[], int top, int bot, string f)
{
if (top > bot)
return -1;
else
int mid = (top + bot)/2;
if (f == A[Mid])
return Mid;
else if (f < A[Mid])
return BS(A, top, Mid-1, f);
else if (f > A[Mid])
return BS(A, Mid+1, bot, f);
}
Generic Programming
Goal: To build algo that are able to operate on many different types of data
ex) Sort function that sorts string, ints, and Student objects, etc.
Custom comparison operators
bool operator >= (const Dog &a, const Dog &b)
{
if (a.getWeight() >= b.getWeight) eturn true;
else return false;
}
main ()
{
Dog fido(5), spot(3);
if (fido >= spot)
{
cout << "fido wins";
}
}
As we can see in operator >=
declaration, since a and b are const
, our function can only call const
functions in class Dog. getWeight()
should be const
too!
If we forget the const
keyword, we will see the compile error!
Template
template <typename Item>
void swap (Item &a, Item &b)
{
Item temp;
temp = a;
a = b;
a = temp;
}
// use our templated func
main()
{
Dog d1(10), d2(20);
swap (d1, d2);
Circle c1(10), c2(20);
swap (c1, c2);
}
Now Swap()
works both as SwapCircle()
and SwapDog()
Function Template Details
You must use the template data type to define the type of at least one formal parameter, or you'll get an ERROR!
In classes with externally defined member functions, things get ugly!
Can add template <typename xxx>
before the class declaration itself, and before each definition, outside the class
STL Class: Vector
The STL vector is a template class that works just like an array, only it doesn't have a fixed size!
Vectors grow/shrink automagically when you add/remove items.
Reference
この問題について(CS 32 Lecture 9. Recursion(2), Generic programming), 我々は、より多くの情報をここで見つけました
https://velog.io/@hojin11choi/CS-32-Lecture-9.-Recursion2-Generic-programming
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
int findPos(int *curr, int num)
{
if (!curr)
return -1;
if (curr->val == num)
return 0;
if (findPos(cur->next, num) == -1)
return -1;
else
return 1+findPos(cur->next, num);
}
Be careful!! Recursion can be a pig when it comes to memory usage!
Never let your recursive calls get too deep!
Binary Search
Goal: Search a sorted array of data for a particular item
Idea: Use recursion and a divide-and-conquer approach!// pseudocode
Search(sortedWordList, findWord)
{
if no word in the list
not found
if findWord == middle word
found
if findWord < middle word
Search(first half of sortedWordList);
else
Search(second half of sortedWordList);
}
int BS(string A[], int top, int bot, string f)
{
if (top > bot)
return -1;
else
int mid = (top + bot)/2;
if (f == A[Mid])
return Mid;
else if (f < A[Mid])
return BS(A, top, Mid-1, f);
else if (f > A[Mid])
return BS(A, Mid+1, bot, f);
}
Generic Programming
Goal: To build algo that are able to operate on many different types of data
ex) Sort function that sorts string, ints, and Student objects, etc.
Custom comparison operators
bool operator >= (const Dog &a, const Dog &b)
{
if (a.getWeight() >= b.getWeight) eturn true;
else return false;
}
main ()
{
Dog fido(5), spot(3);
if (fido >= spot)
{
cout << "fido wins";
}
}
As we can see in operator >=
declaration, since a and b are const
, our function can only call const
functions in class Dog. getWeight()
should be const
too!
If we forget the const
keyword, we will see the compile error!
Template
template <typename Item>
void swap (Item &a, Item &b)
{
Item temp;
temp = a;
a = b;
a = temp;
}
// use our templated func
main()
{
Dog d1(10), d2(20);
swap (d1, d2);
Circle c1(10), c2(20);
swap (c1, c2);
}
Now Swap()
works both as SwapCircle()
and SwapDog()
Function Template Details
You must use the template data type to define the type of at least one formal parameter, or you'll get an ERROR!
In classes with externally defined member functions, things get ugly!
Can add template <typename xxx>
before the class declaration itself, and before each definition, outside the class
STL Class: Vector
The STL vector is a template class that works just like an array, only it doesn't have a fixed size!
Vectors grow/shrink automagically when you add/remove items.
Reference
この問題について(CS 32 Lecture 9. Recursion(2), Generic programming), 我々は、より多くの情報をここで見つけました
https://velog.io/@hojin11choi/CS-32-Lecture-9.-Recursion2-Generic-programming
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
// pseudocode
Search(sortedWordList, findWord)
{
if no word in the list
not found
if findWord == middle word
found
if findWord < middle word
Search(first half of sortedWordList);
else
Search(second half of sortedWordList);
}
int BS(string A[], int top, int bot, string f)
{
if (top > bot)
return -1;
else
int mid = (top + bot)/2;
if (f == A[Mid])
return Mid;
else if (f < A[Mid])
return BS(A, top, Mid-1, f);
else if (f > A[Mid])
return BS(A, Mid+1, bot, f);
}
Goal: To build algo that are able to operate on many different types of data
ex) Sort function that sorts string, ints, and Student objects, etc.
Custom comparison operators
bool operator >= (const Dog &a, const Dog &b)
{
if (a.getWeight() >= b.getWeight) eturn true;
else return false;
}
main ()
{
Dog fido(5), spot(3);
if (fido >= spot)
{
cout << "fido wins";
}
}
As we can see in operator >=
declaration, since a and b are const
, our function can only call const
functions in class Dog. getWeight()
should be const
too!If we forget the
const
keyword, we will see the compile error! Template
template <typename Item>
void swap (Item &a, Item &b)
{
Item temp;
temp = a;
a = b;
a = temp;
}
// use our templated func
main()
{
Dog d1(10), d2(20);
swap (d1, d2);
Circle c1(10), c2(20);
swap (c1, c2);
}
Now Swap()
works both as SwapCircle()
and SwapDog()
Function Template Details
You must use the template data type to define the type of at least one formal parameter, or you'll get an ERROR!
In classes with externally defined member functions, things get ugly!
Can add
template <typename xxx>
before the class declaration itself, and before each definition, outside the classSTL Class: Vector
The STL vector is a template class that works just like an array, only it doesn't have a fixed size!
Vectors grow/shrink automagically when you add/remove items.
Reference
この問題について(CS 32 Lecture 9. Recursion(2), Generic programming), 我々は、より多くの情報をここで見つけました https://velog.io/@hojin11choi/CS-32-Lecture-9.-Recursion2-Generic-programmingテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol