# Recursion: Conceptual

Recursion gives you a new perspective on problem-solving by defining a problem in terms of itself.

Start## Key Concepts

Review core concepts you need to learn to master this subject

Base Case of a Recursive Function

Recursive Step in Recursive Function

What is Recursion

Call Stack in Recursive Function

Big-O Runtime for Recursive Functions

Weak Base Case in Recursive Function

Execution Context of a Recursive Function

Base Case of a Recursive Function

Base Case of a Recursive Function

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

A recursive function should have a base case with a condition that stops the function from recursing indefinitely. In the example, the base case is a condition evaluating a negative or zero value to be true.

Recursive Step in Recursive Function

Recursive Step in Recursive Function

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

A recursive function should have a **recursive step** which calls the recursive function with some input that brings it closer to its base case. In the example, the recursive step is the call to `countdown()`

with a decremented value.

What is Recursion

What is Recursion

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

Recursion is a strategy for solving problems by defining the problem in terms of itself. A recursive function consists of two basic parts: the base case and the recursive step.

Call Stack in Recursive Function

Call Stack in Recursive Function

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

Programming languages use a facility called a **call stack** to manage the invocation of recursive functions. Like a stack, a call stack for a recursive function calls the last function in its stack when the **base case** is met.

Big-O Runtime for Recursive Functions

Big-O Runtime for Recursive Functions

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

The big-O runtime for a recursive function is equivalent to the number of recursive function calls. This value varies depending on the complexity of the algorithm of the recursive function. For example, a recursive function of input N that is called N times will have a runtime of O(N). On the other hand, a recursive function of input N that calls itself twice per function may have a runtime of O(2^N).

Weak Base Case in Recursive Function

Weak Base Case in Recursive Function

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

A recursive function with a weak base case will not have a condition that will stop the function from recursing, causing the function to run indefinitely. When this happens, the call stack will overflow and the program will generate a *stack overflow* error.

Execution Context of a Recursive Function

Execution Context of a Recursive Function

```
function countdown(value)
if value is negative or zero
print "done"
otherwise if value is greater than zero
print value
call countdown with (value-1)
```

An execution context of a recursive function is the set of arguments to the recursive function call. Programming languages use execution contexts to manage recursive functions.

- 1You’ve heard about a trendy new spot that sells fruit sandwiches. What are fruit sandwiches? You have no idea, but you’re eager to find out! Sadly, when you arrive at the store, the line is out t…
- 2Recursion is a strategy for solving problems by defining the problem in terms of itself. For example, to
**sum the elements of a list**we would take the first element and add it to the **sum of t… - 3A recursive approach requires the function invoking itself
**with different arguments.**How does the computer keep track of the various arguments and different function invocations if it’s the sa… - 4Recursion has two fundamental aspects: the base case and the recursive step. When using iteration, we rely on a counting variable and a boolean condition. For example, when iterating through the …

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory