Recursion in C++ Programming
Recursion in C++ programming involves functions that call themselves to solve tasks efficiently. Learn about recursive functions, iterative approaches, comparisons, and examples like calculating factorials and Fibonacci numbers. Explore the efficiency and differences between iterative and recursive solutions with practical code examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Recursion Andy Wang Object Oriented Programming in C++ COP 3330
Recursion A recursive function is a function that calls itself Many tasks can be done with either recursion or with iteration Iteration involves a loop, but not recursive calls Make sure the recursion stops at some point Infinite recursion will result in a crash, when stack frames overrun the limit
One example: Factorials n! = n*(n 1)*(n 2) *1 Iteratively, we can define a function as follows unsigned long Factorial(int n) { unsigned long f = 1; for (int j = n; j >= 1; j--) f *= I; return f; }
One example: Factorials But, notice that n! = n*(n 1)*(n 2) *1 = n*(n 1)! We can define a recursive function unsigned long Factorial(int n) { if (n <= 1) return 1; else return (n*Factorial(n 1)); }
One example: Factorials The recursive function will end when n = 1 Each recursive call will call the function with a smaller n So, which is better? The performance is similar in this case Recursive version uses more memory Each recursive call takes one stack frame
Is Recursion Better? Depends! Let s check out the Fibonnaci example A Fibonnaci number is defined recursively First and the second elements are both 1 Nth element is the sum of elements n 1 and n 2 Fib(n) = Fib(n 1) + Fib(n 2)
Is Recursion Better? Iterative Fibonnaci function int Fib(int n) { int n1 = 1, n2 = 1, n3; int j = 2; while (j < n) { n3 = n1 + n2; n2 = n3; n1 = n2; j++; } return n }
Is Recursion Better? Recursive Fibonnaci function int Fib(int n) { if (n <= 0) return 0; else if (n == 1) return 1; else return Fib(n 1) + Fib(n 2); }
Which One is More Efficient? Try them out! http://www.cs.fsu.edu/~myers/cop3330/examples/recursi on/fib.cpp Fib 10, 20, 30, 40, 50 Iterative version is definitely faster
Recursion vs. Iteration Any recursive solution can be done iteratively A recursive solution is often easier to code Recursion does involve extra overhead Function calls, stack frames Iterative solutions are typically faster
Sorting Algorithms Many solutions You ve probably seen bubble sort and selection sort Two sort algorithms (often written with recursion) are much faster Quick sort Merge sort
GCD Example http://www.cs.fsu.edu/~myers/gaddis/Chapter%2019/P r19-5.cpp Compute the greatest common divisor
Pr19-5.cpp #include <iostream> using namespace std; int gcd(int x, int y) { if (x % y == 0) return y; else return gcd(y, x % y); } int main() { int num1, num2; cout << Enter two integers: ; cin >> num1 >> num2; cout << The GDC of << num1 << and << num2 << is << gcd(num1, num2) << endl; return 0; }
More Recursion Examples http://www.cs.fsu.edu/~myers/savitch3c++/Ch13/ 13-01.cpp: write a number vertically using recursion 13-02.cpp: write a number vertically using iteration 13-03.cpp: raise a number to a power of n (recursion) 13-06.cpp: binary search (recursion) 13-08.cpp: binary search (iteration)
13-01.cpp #include <iostream> using namespace std; void writeVertical(int n) { if (n < 10) { cout << n << endl; } else { writeVertical(n/10); cout << (n % 10) << endl; } }
13-01.cpp int main() { cout << writeVertical(3): << endl; writeVertical(3); cout << writeVertical(12): << endl; writeVertical(12); cout << writeVertical(123): << endl; writeVertical(123); return 0; }
13-02.cpp Power of ten that has the same number of digits as n (nsTens = 1000 if n = 2345) #include <iostream> using namespace std; void writeVertical(int n) { int nsTens = 1; int leftEndPiece = n; while (leftEndPiece > 9) { leftEndPiece = leftEndPiece / 10; nsTens = nsTens*10; } for (int powerOf10 = nsTens; powerOf10 > 0; powerOf10 = powerOf10/10) { cout << (n/powerOf10) << endl; n = n % powerOf10; } }
13-02.cpp int main() { cout << writeVertical(3): << endl; writeVertical(3); cout << writeVertical(12): << endl; writeVertical(12); cout << writeVertical(123): << endl; writeVertical(123); return 0; }
13-03.cpp #include <iostream> #include <cstdlib> using namespace std; int power(int x, int n) { if (n < 0) { cout << Illegal argument to power.\n ; exit(1); } if (n > 0) return (power(x, n 1)* x); else // n == 0 return 1; }
13-03.cpp int main() { for (int n = 0; n < 4; n++) { cout << 3 to the power << n << is << power(3, n) << endl; } return 0; }
13-06.cpp #include <iostream> using namespace std; const int ARRAY_SIZE = 10; void search(const int a[], int first, int last, int key, bool &found, int &location) { int mid; if (first > last) found = false else { mid = (first + last/2) if (key == a[mid]) { found = true; location = mid; } else if (key < a[mid] search(a, first, mid 1, key, found, location); else if (key > a[mid] search(a, mid + 1, last, key, found, location); } }
13-06.cpp int main() { int a[ARRAY_SIZE]; cout << Array contains:\n ; for (int j = 0; j < ARRAY_SIZE; J++) { a[j] = 3*j; cout << a[j] << ; } cout << endl;
13-06.cpp int key, location; bool found; cout << Enter number to be located: ; cin >> key; search(a, 0, ARRAY_SIZE 1, key, found, location); if (found) cout << key << is in index location << location << endl; else cout << key << is not in the array. << endl; return 0; }
13-06.cpp #include <iostream> using namespace std; const int ARRAY_SIZE = 10; void search(const int a[], int lowEnd, int highEnd, int key, int first = lowend, last = highEnd, mid; found = false; while ((first <= last) && !found) { mid = (first + last)/2 if (key == a[mid]) { found = true; location = mid; } else if (key < a[mid]) last = mid 1; } else if (key > a[mid]) first = mid + 1; }
13-08.cpp int main() { int a[ARRAY_SIZE]; cout << Array contains:\n ; for (int j = 0; j < ARRAY_SIZE; J++) { a[j] = 3*j; cout << a[j] << ; } cout << endl;
13-08.cpp int key, location; bool found; cout << Enter number to be located: ; cin >> key; search(a, 0, ARRAY_SIZE 1, key, found, location); if (found) cout << key << is in index location << location << endl; else cout << key << is not in the array. << endl; return 0; }
