# Chapter 8 : Recursion

### Topics covered in this snack-sized chapter:

#### Recursion arrow_upward

• Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub-problems until you get to a small enough problem that it can be solved trivially.
• Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
• Recursion is an alternative to iteration (loop):
• Often more "elegant” and concise than a loop.
• Sometimes very inefficient.
• Recursion should be considered when:
• A problem can be defined in terms of successive smaller problems of the same type, i.e. recursively.
• Eventually the problem gets small enough that the answer is known (base case).
• Reducing the problem size leads to the base case.
• Sometimes the "work" of the algorithm is done after the base case is reached.

• #### The Three Laws of Recursion arrow_upward

• All recursive algorithms must obey three important laws:
• A recursive algorithm must have a base case.
• A recursive algorithm must change its state and move toward the base case.
• A recursive algorithm must call itself, recursively.

 Base Case if (answer is known) provide the answer. Recursive Case make a recursive call to solve a smaller version of the same problem

#### Direct Recursion arrow_upward

• A function calls by itself is known as direct recursion.

• #### Indirect Recursion arrow_upward

• Indirect Recursion is when a function calls a second function which in turn calls the first function.

• #### Recursive Definitions                arrow_upward

• A recursive formula always uses the preceding term to define the next term of the sequence.
• N!, for any positive integer N, is defined to be the product of all integers between 1 and N inclusive.
• This definition can be expressed recursively as:
•      1!  =  1

N!  = N * (N-1)!

• The concept of the factorial is defined in terms of another factorial.
• Eventually, the base case of 1! is reached.

• #### Cases in Recursion arrow_upward

###### Base case:

• A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.

• ###### Recursive Case:

• A case which returns to the answer which is closer.

• ###### Run-time Stack:

• A run time stack used for saving the frame stack of a function when every recursion or every call occurs.

• ###### Tail Recursion:

• It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

• #### Thank You from Kimavi arrow_upward

• Please email us at Admin@Kimavi.com and help us improve this tutorial.

• Kimavi - A Video Learning Library { Learning is Earning }

Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only \$10 a month