FUNCTION RECURSION

Group 4
RECURSIVE DEFINITIONS

It involve functions that call themselves to solve a

problem. Recursion is a common mathematical and
programming concept. It means that a function calls
itself. This has the benefit of meaning that you can
loop through data to reach a result. The key to using
recursion effectively is to have a well-defined base
case and a recursive case. Here's a general approach
to defining a recursive function:
1.Base Case: This is the condition under which the
recursion will stop. It prevents the function from
calling itself indefinitely.

2.Recursive Case: This is where the function calls

itself with modified arguments. The goal is to break
the problem down into simpler subproblems that
eventually reach the base case.
EXAMPLE

OUTPUT
B A S I C P R O P E RT I E S O F
RECURSION
1.Base Case
a.The condition that stops the recursion.
b.Prevents the function from calling itself forever.
2.Recursive Case
a.The part of the function where it calls itself with a modified
argument.
b.Helps break the problem into smaller parts.
3.Termination
a.A recursive function must always reach a base case to
stop recursion.
4.Stack Usage
a.Each recursive call uses a new frame in the call stack.
b.Too many recursive calls can lead to stack overflow.
TA I L R E C U R S I O N
DEFINITION
 Tail recursion occurs when the recursive call is the last
operation in the function.
 There is no additional work to be done after the recursive call
returns.

PROPERTIES
 Optimization: Some languages or compilers can optimize
tail recursion to avoid adding new frames to the call stack,
making it as efficient as an iterative solution.
EXAMPLE

OUTPUT
N O N -TA I L R E C U R S I O N
DEFINITION
 Non-tail recursion occurs when the recursive call is followed
by additional operations or computations.
 The function must do more work after the recursive call
returns.

PROPERTIES
 Stack Usage: Each recursive call adds a new frame to the
stack, potentially leading to high memory usage.
 Performance: Less efficient compared to tail recursion in
EXAMPLE

OUTPUT
INDIRECT RECURSION
DEFINITION
 Indirect recursion occurs when a function calls another
function, which in turn calls the original function, creating a
loop of function calls.
 Unlike direct recursion, where a function calls itself, indirect
recursion involves multiple functions interacting with each
other.
 Indirect recursion is useful in scenarios where a problem
naturally fits into a multi-step process involving multiple
EXAMPLE

OUTPUT
NESTED RECURSION
 Occurs when a recursive function calls itself in a way
that involves multiple levels of recursion.
 A function makes a recursive call that itself involves
further recursive calls.
 This type of recursion can become quite complex
because it involves multiple layers of recursive calls.
EXAMPLE
Suppose you want to count the number of distinct paths from the top-left
corner to the bottom-right corner of an m x n grid, where you can only move
right or down. The function will use nested recursion to solve the problem.
OUTPUT
E XC E SS I V E R E C U R S I O N
 Occurs when a recursive function makes too many recursive
calls, leading to inefficient performance or runtime errors.
 This can happen due to deep recursion, a high number of
recursive calls, or poorly defined base cases.
P R O B L E M S W / E XC E SS I V E
RECURSION
1. Stack Overflow: Each recursive call adds a new frame
to the call stack. If the recursion depth is too high, it can
exceed the stack limit and cause a stack overflow error.

2. Performance Issues: Excessive recursion can lead to

high time complexity, especially if the function performs
redundant calculations or if the recursion depth is very large.

3. Memory Usage: Deep recursion can consume significant

memory, as each call occupies stack space. This can lead to
inefficient use of resources and potentially crash the program.
EXAMPLE

For large values of n, this function can make too many recursive calls and potentially
cause a stack overflow.
OUTPUT
BACKTRACKING
 A problem-solving technique used to find solutions by
exploring all possible options and undoing choices when they
lead to dead ends.
 It's particularly useful for problems that involve finding a
solution from a set of constraints or exploring all possibilities.
KEY CONCEPTS OF
BACKTRACKING
1.Choice: At each step, make a choice among the available
options.
2.Constraint: Ensure that the choice satisfies the problem
constraints.
3.Backtrack: If the choice leads to an invalid solution or a
dead end, undo the choice and try another option.
4.Base Case: Determine when to stop the recursion (e.g.,
when a valid solution is found or when all possibilities have
EXAMPLE
Example we'll generate all possible sequences of binary digits (0s
and 1s) of length n.
OUTPUT
 BENEFITS OF RECURSION
1.Simplifies Code: Recursive solutions are often more concise
and easier to understand, especially for problems with self-
similar structures like trees.

2.Eases Problem Decomposition: Recursion breaks

problems into smaller sub-problems, making it easier to
manage complex tasks, such as in divide-and-conquer
algorithms.

3.Improves Code Organization: Recursive functions can lead

to cleaner, more modular code, as each call handles a
smaller part of the problem.
 BENEFITS OF RECURSION
4. Facilitates Backtracking: Essential for exploring all
possible solutions, useful in problems like the Binary
sequence.

5. Handles Complex Problems: Ideal for traversing recursive

structures like trees and graphs, making algorithms like
depth-first search straightforward.

Recursion can make code more intuitive and manageable,

especially for complex or hierarchical problems.
 C O M M O N I SS U E S W /
1.Stack Overflow: R E C U R S I O N
o Each recursive call adds a new frame to the call stack. Deep or
infinite recursion can exceed the stack limit, causing a stack
overflow error.

2.Performance Concerns:
o Recursion can lead to redundant calculations and inefficient
performance, especially in cases like calculating Fibonacci
numbers.

3.High Memory Usage:

o Description: Each recursive call uses memory for stack
frames. Deep recursion can consume significant memory
resources.
 C O M M O N I SS U E S W /
RECURSION
4.Difficult Debugging:
o Description: Recursive functions can be harder to debug due
to complex call stacks and deep recursion.

5.Complexity in Understanding:
o Description: Recursion can be challenging to grasp and
manage, especially for those new to programming.

6.Incorrect Base Cases:

o Description: Failing to define or correctly handle base cases
can lead to infinite recursion and incorrect results.