Recursion and Factorial Functions

Recursion

• Recursion is a programming technique where a function calls itself.
• It's not a data structure, but a problem-solving approach.
• Recursion is used to solve problems defined in terms of smaller instances of the same problem (divide and conquer).
• Recursion involves a base case (stopping condition) to avoid infinite loops.
• Recurrence relations define relationships between a big problem and smaller subproblems.
• Function calls form a call stack, creating a series of nested function calls.
• Recursive function calls follow a specific pattern of execution, which influences the program's output.

Function Calls (Example)

• Methods/functions are blocks of code.
• Methods typically return data.
• Methods can have parameters, which are values passed to the function.
• Function calls create nested calls, and execution follows the call stack.
• Output is based on the order calls are made and handled.

Factorial Recurrence Relation

• Factorial is a mathematical operation.
• Factorial is defined recursively (n! = n * (n-1)!).
• The factorial of a number is a product of all positive integers less than or equal to that number.
• The base case in factorial is when n = 1

Factorial Function (Example)

• Recursive functions can calculate the factorial of a non-negative integer.
• The base case/termination condition is important in recursion to end the repetitive calls.
• Recursion involves repetitive calls of the same function.

Print n to 1 (Example)

• A function can print numbers in a descending sequence from n to 1.
• The function calls itself recursively to achieve this.
• The base case is n= 0, where the function returns or ends the calls.

Print 1 to n (Extra Parameter)(Example)

• A function can also take a parameter to determine the upper limit, n, for printing numbers from 1 to n.
• The parameter makes the output dynamic.
• The function calls itself recursively to print numbers up to n.
• The base case stops recursion when the function reaches the input value.

Print Sum 1 to n(Parametrised)

• A function can iterate through a range and calculate the sum.
• The parameter lets the output be dynamic.
• Summing numbers from 1 to n can use recursion or iterative approaches.
• The function must define a base case.

Print Sum 1 to n (Return Type) (Example)

• A function that returns an integer value.
• The function can calculate the sum recursively.

Power Function (Logarithmic)

• Calculating a raised to the power b using recursion.
• Recursive calculations can take different levels of time based on the specific calculations required.

Multiple Calls (Fibonacci Sequence)

• Recursion (Fibonacci) demonstrates repeated calls.
• The recursive function calculates the nth Fibonacci number.
• The base case for the Fibonacci function is when n is 0 or 1.

Stair Path

• Counting ways to reach a particular stair.
• Using recursion to count the number of possible ways to go up stairs.
• This is similar to the Fibonacci sequence.

Maze Path

• Counting the ways to go through a maze.
• The function counts the number of unique paths through the maze to reach the target.

Pre In Post

• Order of function calls.
• Order of statements when calling a method.

Call Stack

• A concept in programming that tracks the function calls.
• The function calls build up and down in order according to the call stack.
• Error tracing can be done when looking for issues in a recursion program.

Skip a character (Example)

• Function that removes/skips a given character in a string.
• This creates a new string with the given character removed.
• The function uses recursion to iterate through the string and remove specified characters.

Subsets

• Generating all subsets of a string.
• Producing all the subsets from unique characters in a string.

Permutations

• Generating the permutations/ordering of a string.
• Generating all possible orderings of the elements of a string.

Greatest Common Divisor (GCD)

• Finding the greatest common divisor of two numbers.
• Euclid's algorithm can also calculate the greatest common divisor.
• The algorithm recursively computes gcd to obtain the greatest common divisor.