// recursion.cpp
#include <iostream>
#include "cmpt_error.h"
using namespace std;
//
// This file gives some examples of using recursion with basic functions,
// and also with with singly-linked lists using the List class.
//
//
// The factorial of n is defined as:
//
// n! = 1 * 2 * 3 * ... * n
//
// 0! is a special case, and is defined to be equal to 1.
//
// Another way to define factorials is to use a recurrence relation like
// this:
//
// f(0) = 1
// f(n) = n * f(n - 1) // recursive case
//
// This definition is actually more precise than the previous one because
// it does not use "..." anywhere.
//
// It is actually quite straightforward to convert the recurrence relation
// into a C++ function as shown below.
//
// In practice, recursion is often less efficient than non-recursive code
// that does the same thing because recursion requires a lot of function
// calls. However, many tricky programming problems are best solved
// through recursive solutions. If an actual recursive implementation of
// the solution is too slow, then it can be converted to a non-recursive
// solution.
//
// This definition is an example of linear recursion, which means that on
// each call to factorial only one recursive call is made.
int factorial(int n) {
if (n == 0) { // base case
return 1;
} else {
return n * factorial(n - 1); // recursive case
}
}
// 0! = 1
// 1! = 1
// 2! = 2
// 3! = 6
// 4! = 24
// 5! = 120
// 6! = 720
// 7! = 5040
// 8! = 40320
// 9! = 362880
// 10! = 3628800
void test1() {
for(int i = 0; i <= 10; ++i) {
cout << i << "! = " << factorial(i) << "\n";
}
}
// The Fibonacci numbers are an interesting example of recursion, and are
// defined like this:
//
// F(1) = 1
// F(2) = 1
// F(n) = F(n-1) + F(n-2), n > 2
//
int call_count; // global variable to count # of times rec_fib called
int rec_fib(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
call_count += 2;
return rec_fib(n-1) + rec_fib(n-2);
}
}
void test2() {
for(int i = 1; i <= 100; ++i) {
call_count = 1;
int result = rec_fib(i);
cout << "rec_fib(" << i << ") = " << result
<< ", call_count = " << call_count << "\n";
}
}
//
// rec_fib mirrors the mathematical definition of Fibonacci numbers, which
// makes it easy to implement in a correct way. However, it does a huge
// number of function calls, making it practically useless for calculating
// large Fibonacci numbers.
//
// It is possible to write a recursive Fibonacci function that is more
// efficient, but it requires some extra work. In what follows, by
// returning pairs of Fibonacci numbers we can calculate them much more
// efficiently.
//
// While this function is much faster, it is much more work to implement
// correctly.
//
//
// Note that C++ has a standard Pair type in <utility>, e.g.:
//
// std::Pair<int, int> p{1, 2};
//
// In practice you would usually want to use that (because it works with
// any types, and has some useful features), but here we write our own
// Pair for simplicity.
struct Pair {
int first, second;
};
Pair linear_rec_fib_helper(int n) {
if (n <= 1) {
return Pair{n, 0};
} else {
call_count += 1;
Pair p = linear_rec_fib_helper(n-1);
return Pair{p.first + p.second, p.first};
}
}
int linear_rec_fib(int n) {
Pair p = linear_rec_fib_helper(n);
return p.first;
}
void test3() {
for(int i = 1; i <= 100; ++i) {
call_count = 1;
int result = linear_rec_fib(i);
cout << "rec_fib(" << i << ") = " << result
<< ", call_count = " << call_count << "\n";
}
}
// Linked lists functions can often be implemented recursively. For
// example, in the List class below, the recursive functions print_forward
// and print_reverse have been added.
class List {
private:
struct Node {
int val;
Node* next;
}; // struct Node
Node* head;
void print_forward(Node* p) const {
if (p == nullptr) {
// do nothing
} else {
cout << p->val << " "; // print the first element
print_forward(p->next); // recursively print the rest
}
}
public:
// Default constructor: creates a new empty list.
List()
: head(nullptr)
{ }
// Destructor: called automatically when this list goes out of scope,
// or is deleted. Thus no memory leaks are possible!
~List() {
while (head != nullptr) {
Node* p = head;
head = head->next;
delete p;
}
cout << "List destructor: all list elements deleted\n";
}
bool is_empty() const {
return head == nullptr;
}
int size() const {
int count = 0;
Node* p = head;
while (p != nullptr) {
count++;
p = p->next;
}
return count;
}
void push(int x) {
head = new Node{x, head};
}
int pop() {
if (is_empty()) cmpt::error("can't pop empty list");
Node* p = head;
head = head->next;
int result = p->val;
delete p;
return result;
}
void print() const {
cout << "[";
Node* p = head;
while (p != nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << "]";
}
void println() const {
print();
cout << "\n";
}
void print_forward() const {
print_forward(head);
}
// void print_reverse() const {
// }
}; // class List
void test4() {
List lst;
lst.push(1);
lst.push(2);
lst.push(3);
lst.push(4);
lst.print_forward();
cout << "\n";
}
int main() {
// test1();
// test2();
// test3();
test4();
}