Module 6: Recursion Lecture Notes

Practice flashcards covering the definitions, logic, and mathematical applications of recursion as presented in the Module 6 lecture.

Recursive Call

A function call in which the function being called is the same as the one making the call.

Recursion

A powerful programming technique in which procedures and functions call themselves, used in place of iteration (looping).

Infinite Recursion

A recursive function that lacks code to stop it from repeating, causing it to act like an infinite loop.

Depth of Recursion

The number of times a function calls itself before reaching a base case; for example, a call to message(5) results in a depth of 6 if it terminates at 0.

Base Case

The case for which a solution is explicitly known and can be stated non-recursively, allowing a recursive function to terminate.

General Case

The case for which the solution is expressed in a smaller version of itself, also known as the Inductive Step Case or recursive case.

numChars function

A recursive function used to count occurrences of a character in a string using parameters for the search character, the string array, and the starting subscript.

Direct Recursion

Examples of recursive functions that directly call themselves.

Indirect Recursion

A programming situation that occurs when function A calls function B, which in turn calls function A.

Factorial Recursive Definition

Mathematically defined as $Factorial(n) = n \times Factorial(n - 1)$ if $n > 0$, and $1$ if $n = 0$.

Greatest Common Divisor (GCD)

Using Euclid's Algorithm, $GCD(x, y)$ is $y$ if $y$ divides $x$ evenly; otherwise, it is GCD(y, x \text{ % } y), where x \text{ % } y is the remainder of $x/y$.

Fibonacci Series

A sequence of numbers defined as $F_0 = 0$, $F_1 = 1$, and $F_N = F_{N-1} + F_{N-2}$ for $N \times 2$.

FloatList::countNodes

A recursive linked list operation where the base case returns 0 if the pointer is NULL, and otherwise returns $1 + \text{countNodes(nodePtr->next)}$.

FloatList::showReverse

A recursive operation that displays linked list nodes in reverse order by calling itself for the next node before printing the current node's value.