Recursive Function

Algorithm and Complexity

Recursion

It is a method of solving a problem by breaking it down into smaller subproblems

The Three Laws of Recursion

1. Must have a Base Case

2. Must change state and move toward the base case

3. Must call itself recursively

Conditions

These are used to start, continue, and stop the algorithm.

• The start and continue can be the same

• The stop is considered a base case

Call Stack

Managing function calls and keep track of program execution.

Direct Recursion

A function that calls itself from within

Indirect Recursion

More than one function calls another in a circular manner

Tail Recursion

The call is the last statement that is executed

Head Recursion

The call is the first statement that is executed

Tree Recursion

Calls itself multiple times

Nested

Recursion in a Recursion

Form 1

Form 2

Form 3

Form 4

Tail Recursion - Visual Representation

Head Recursion - Visual Representation

Tree Recursion - Visual Representation

Nested Recursion - Visual Representation

Indirect Recursion - Visual Representation