Study sheet: C++ Functions Recursion and OOP

📋 Course Outline

1. Data Structures and C++ Origins
2. C++ Environment and First Programs
3. Core C++ Syntax and Data
4. Strings, Input, and Identifiers
5. Namespaces, Constants, and Formatting
6. Functions and Standard Libraries
7. Character and String Manipulation
8. Function Calls and Overloading
9. Function Templates
10. Recursion and Induction
11. Recursive Numerical Algorithms
12. Recursive Arrays and Strings
13. Classes Objects and Encapsulation
14. Constructors and Initialization
15. Constructor Overloading and Initialization
16. Member Initialization and Class Pointers
17. Inheritance and Derived Classes
18. Building Programs from Multiple Files

📖 1. Data Structures and C++ Origins

🔑 Key Concepts & Definitions

• Data Structure : A logical or mathematical model for collecting and organizing data so that operations can be performed effectively.
• Algorithm : A set of instructions or rules for solving a problem or accomplishing a task, especially through computer calculations.

★ Must-know

• C++ combines object-oriented programming with procedural C and is therefore a multiparadigm language suitable for system software such as operating systems.

Further detail

• C++ was developed by Bjarne Stroustrup at Bell Labs as an extension of the C language.

💡 Memory Hook

C with Classes → C++ → multiparadigm system language

📖 2. C++ Environment and First Programs

★ Must-know

• A C++ development environment requires a text editor for writing code and a compiler for translating code into a language understood by the computer.

• A basic Linux workflow creates a source file, compiles it with $g++ -o hello hello.cpp$, and runs the executable with $./hello$.

Further detail

• Examples of integrated development environments include:

  • Code::Blocks
  • Eclipse
  • Sublime Text
  • Visual Studio

• GCC is the GNU Compiler Collection, which provides compiler front-ends for C, C++, Objective-C, Fortran, Ada, and Go and includes runtime support libraries.

💡 Memory Hook

Write → compile → run

📖 3. Core C++ Syntax and Data

🔑 Key Concepts & Definitions

• cout : The standard output object used with the stream insertion operator << to print values or text.
• cin : The standard input object used with the stream extraction operator >> to read data from the keyboard.

★ Must-know

• A C++ program must include directives and at least one function named main, whose body contains executable statements.

Further detail

• Every C++ statement ends with a semicolon, and the compiler ignores whitespace.

💡 Memory Hook

cout outputs, whereas cin inputs

📖 4. Strings, Input, and Identifiers

🔑 Key Concepts & Definitions

• String : An object or sequence used for storing text as a collection of characters.

📝 Essential Points

• Primitive types include:
  • int
  • float
  • double
  • boolean
  • char

📌 The extraction operator >> reads only one word from a string input because whitespace terminates the input.

• 🔄 Reading a complete line after formatted input requires:

  1. Read the formatted input
  2. Call cin.ignore()
  3. Call getline(cin, variable)

• C++ identifier rules are:

  • Contain letters, digits, and underscores
  • Begin with a letter or underscore
  • Remain case-sensitive
  • Exclude whitespace and special characters
  • Exclude reserved words

💡 Memory Hook

cin stops at whitespace, whereas getline reads the line

📖 5. Namespaces, Constants, and Formatting

🔑 Key Concepts & Definitions

• Namespace : A declarative region that gives identifiers such as types, functions, and variables a distinct scope.
• Symbolic Constant : A named constant whose initialized value cannot be changed.

★ Must-know

📌 Entities in a namespace can be accessed from outside it with the scope resolution operator ::, such as namesp1::value().

Further detail

• The setw() manipulator, declared in <iomanip>, sets the field width for the next insertion operation.

• Integer-base manipulators are:

  • dec for decimal
  • oct for octal
  • hex for hexadecimal

💡 Memory Hook

Separate namespaces as labeled rooms containing same-named objects

📖 6. Functions and Standard Libraries

🔑 Key Concepts & Definitions

• Function : A complete subprogram designed to perform a well-defined task and may contain input, processing, and output logic.

★ Must-know

📌 C++ functions are either library functions supplied by the standard library or user-defined functions written by the programmer.

📌 A function prototype declares the return type, name, and parameter list followed by a semicolon, allowing the function to be implemented later.

Further detail

📌 A void function returns no value, although its parameter list may be written as empty parentheses or as void.

• The library function sqrt(16) returns 4, and pow(5,3) returns 125.

💡 Memory Hook

Declare → define → call → return

📖 7. Character and String Manipulation

🔑 Key Concepts & Definitions

• C-String : A character array terminated by a null character.

★ Must-know

• Character functions provided through <cctype> include:

  • isdigit
  • isalpha
  • isupper
  • tolower
  • toupper
  • isblank
  • isspace
  • iscntrl

• Common string operations include:

  • strcat appends character arrays
  • strcmp compares strings
  • strlen returns C-string length
  • strcpy copies character arrays
  • push_back inserts a character at the end

Further detail

• For the string object "Rwanda Coding Academy", size(), length(), and strlen(str.c_str()) each return 21.

💡 Memory Hook

string objects provide richer operations, whereas character arrays use null termination

📖 8. Function Calls and Overloading

🔑 Key Concepts & Definitions

• Function call : Transfers execution to the called function until its return statement or the end of the function is reached.

★ Must-know

• A function can be called multiple times with literal arguments, variables, or as part of a larger expression.

📌 C++ permits overloaded functions with the same name when they differ in the number or types of parameters, but return type alone cannot distinguish overloads.

Further detail

• In the example, operate(5,2) selects the integer overload and returns 10, while operate(5.0,2.0) selects the double overload and returns 2.5.

💡 Memory Hook

A function call transfers execution to the function, whereas a declaration only describes it.

📖 9. Function Templates

🔑 Key Concepts & Definitions

• Function template : Defines a generic function whose types are determined when the template is instantiated.

★ Must-know

• A function template is instantiated by calling its name with template arguments in angle brackets followed by the function arguments.

• The generic sum template returns the sum of two values using $T\ sum(T\ a,T\ b)$ and can be instantiated as sum<int>(x,y) or sum<double>(n,m).

Further detail

📌 A template may use multiple type parameters, such as T and U, so its arguments can resolve to different types.

📌 An auto return type lets the compiler deduce a common return type and helps avoid narrowing when a template returns values of different types.

💡 Memory Hook

Picture one function-shaped mold producing versions for different types.

📖 10. Recursion and Induction

🔑 Key Concepts & Definitions

• Recursion : Occurs when a function calls itself to solve a problem through smaller problems of the same nature.
• Principle of Mathematical Induction : Proves a statement for all positive integers by proving a base case, assuming the statement for k, and proving it for k+1.

★ Must-know

• 🔄 The three induction steps are:
  1. Proving the base case
  2. Assuming P(k) for some k
  3. Using that assumption to prove P(k+1)

Further detail

• The induction formula for the sum from 1 to n is $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$.

💡 Memory Hook

Base case → induction hypothesis → induction step.

📖 11. Recursive Numerical Algorithms

★ Must-know

📐 Formula — The factorial recursion is $fact(n)=n\times fact(n-1)$ with the base case $fact(0)=1$.

📐 Formula — The Fibonacci recursion is $f(n)=f(n-1)+f(n-2)$ with base cases f(0)=0 and f(1)=1.

📐 Formula — The recursive power algorithm uses $x^n=x\times x^{n-1}$ with the base case $x^0=1$.

Further detail

📐 Formula — The recursive sum of the digits of n is $sum(n)=sum(\lfloor n/10\rfloor)+(n\bmod 10)$ with sum(0)=0.

📐 Formula — Multiplication by recursion is defined by $multiply(m,n)=multiply(m,n-1)+m$ with multiply(m,0)=0.

💡 Memory Hook

Factorial → Fibonacci → power → digit operations.

📖 12. Recursive Arrays and Strings

🔑 Key Concepts & Definitions

• Palindrome : A sequence that has the same value when read from left to right and from right to left.

★ Must-know

• 🔄 A recursive sorted-array check:
  1. Returns true for zero or one element
  2. Returns false when the first pair is out of order
  3. Checks the array starting at the next element

📐 Formula — The recursive array sum is $sumOfArray(a,n)=a[0]+sumOfArray(a+1,n-1)$ with sumOfArray(a,0)=0.

• To convert a digit string to an integer recursively, the algorithm converts the shorter prefix, multiplies it by 10, and adds the final digit.

Further detail

• A recursive palindrome check compares the first and last elements, returns false when they differ, and recursively checks the inner sequence when they match.

• A recursive character printer stops at '\0' and otherwise prints the first character before recursing on the remaining array.

💡 Memory Hook

Shrink the input → solve the smaller problem → combine or return the result.

📖 13. Classes Objects and Encapsulation

🔑 Key Concepts & Definitions

• Class : A user-defined type or blueprint containing data members and member functions used to create objects.
• Object : An identifiable instance of a class with its own characteristics, behavior, and allocated memory.

★ Must-know

📌 C++ class members can be private, protected, or public: private members are accessible within the class, protected members also within derived classes, and public members from anywhere the object is visible.

• Getters and setters provide public member functions that respectively read and write private data members while preserving encapsulation.

Further detail

📌 Members declared with the class keyword are private by default until another access specifier is encountered.

• Multiple objects of one class have separate member-variable values, so two Rectangle objects can produce different areas from their own widths and heights.

💡 Memory Hook

A class is the type or blueprint, whereas an object is its instantiated variable.

📖 14. Constructors and Initialization

🔑 Key Concepts & Definitions

• Constructor : A special member function with the class name and no return type that runs automatically when an object is created to initialize it.

★ Must-know

📌 Constructors cannot be called explicitly like regular member functions and execute once when a new object of the class is created.

📌 A default constructor takes no parameters and is called when an object is declared without initialization arguments.

Further detail

📌 A constructor can be overloaded with different numbers or types of parameters, and the compiler selects the version matching the object’s initialization arguments.

💡 Memory Hook

A constructor initializes an object automatically, whereas a regular member function must be called.

📖 15. Constructor Overloading and Initialization

🔑 Key Concepts & Definitions

• Constructor : A special member function that initializes an object when it is created and has no return value, not even void.

★ Must-know

📌 A constructor is executed automatically once when a new object is created, whereas it cannot be called explicitly like a regular member function.

📌 An empty pair of parentheses after a class name can declare a function instead of creating an object, so Rectangle rectc(); declares a function returning Rectangle rather than calling the default constructor.

Further detail

• Constructors can be invoked using: functional form with parentheses, assignment initialization with an equal sign, uniform initialization with braces, assignment-style uniform initialization with an equal sign and braces

💡 Memory Hook

Parentheses can declare a function, whereas braces explicitly construct an object.

📖 16. Member Initialization and Class Pointers

🔑 Key Concepts & Definitions

• Pointer to class : A pointer to a class object stores the address of an object whose class is a valid pointer type, such as Rectangle* prect.

★ Must-know

• A constructor can initialize data members in a member initialization list placed after a colon and before the constructor body, such as : width(x), height(y).

• If a member object is omitted from the member initialization list, it is default-constructed before the constructor body executes.

• The arrow operator -> accesses a member through a pointer to an object, while the dot operator . accesses a member directly through an object.

Further detail

📌 Member initialization lists are required when a member class cannot be default-constructed and are useful when default construction would be wasteful before reinitialization.

📌 An array of dynamically allocated class objects is accessed with indexing such as baz[0] and baz[1] and must be released with delete[].

💡 Memory Hook

The dot accesses an object directly, whereas the arrow accesses an object through a pointer.

📖 17. Inheritance and Derived Classes

🔑 Key Concepts & Definitions

• Inheritance : The object-oriented mechanism by which a new class inherits the fields and methods of an existing class and can add its own members.

★ Must-know

📌 Public inheritance is declared with the syntax class ChildClass : public ParentClass { /* additional fields and methods */ };.

• Dog and Cat inherit from Animal and each defines its own sound method, producing “Dog barks” for Dog and “Cat meows” for Cat.

Further detail

• In the example, Animal is the base class, while Dog, Cat, and Cow are derived classes that extend Animal.

💡 Memory Hook

Inheritance from a base class → derived classes reuse and extend its fields and methods.

📖 18. Building Programs from Multiple Files

★ Must-know

📌 A C++ program can use multiple source files either by including a header file or by compiling and linking separate source files with g++ commands.

📌 Separating a class interface in a .h file from its implementation in a .cpp file is good practice, whereas mixing method prototypes and implementations in one header file is identified as bad practice.

• 🔄 A multi-file program is built by:
  1. compiling rectangle.cpp into rectangle.o
  2. compiling program.cpp into program.o
  3. linking rectangle.o and program.o into main

Further detail

📌 A header file can contain a namespace with function definitions, and another source file can access those functions with an #include directive and the namespace.

📌 The preprocessor guard pattern #ifndef Rectangle_H, #define Rectangle_H, declarations, and #endif prevents a header file from being included multiple times.

💡 Memory Hook

Declare → implement → compile objects → link the final executable.

📊 Synthesis Tables

C++ Input and Output

Feature	Operator or function	Role
cout	<<	Outputs values or text
cin	>>	Reads whitespace-delimited input
getline	getline(cin, variable)	Reads a complete line
endl	<< endl	Inserts a newline

C++ Access Specifiers

Specifier	Accessible from class	Accessible from derived class	Accessible elsewhere
private	Yes	No	No
protected	Yes	Yes	No
public	Yes	Yes	Yes