Recursion Lecture Notes

Flashcards covering Recursion, Towers of Hanoi, Factorial, and Fibonacci sequences.

Recursion

A way of solving a problem by having a function call itself.

Towers of Hanoi

A problem that can be solved using recursion. For n=3, it consists of 7 moves.

Tower (N, BEG, AUX, END)

A recursive procedure for solving the Towers of Hanoi problem with N disks.

Base Case (Recursion)

Every recursive function must have one or more base cases that define when the recursion stops.

Recursive Case

Defines how the recursive function calls itself with modified arguments to move towards the base case.

Initialization (Recursion)

Proper initialization of parameters and variables is necessary for recursive functions.

Termination (Recursion)

Recursion must terminate after a finite number of steps.

Stack (Recursion)

Recursion uses the system stack to store intermediate results, so it's important to consider the stack depth.

Factorial (Recursive Function)

A recursive function that calculates the factorial of a number. The base case is factorial(0) = 1, and the recursive call is n * factorial(n-1).

Fibonacci Sequence

A sequence where each term is the sum of the two preceding terms (e.g., 0, 1, 1, 2, 3, 5, 8…). F0=0, F1=1, and Fn = Fn-2 + Fn-1.

FIBONACCI (FIB, N)

A procedure that calculates Fn and returns the value in the first parameter FIB. Uses recursion by calling itself with N-2 and N-1