---
title: "Recursion and the Call Stack"
description: "A function that calls itself on a smaller version of the same problem, with a base case that stops the descent. Every call that has not returned yet waits on the call stack, which is why deep recursio"
canonical: https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e
source: https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Recursion and the Call Stack

A function that calls itself on a smaller version of the same problem, with a base case that stops the descent. Every call that has not returned yet waits on the call stack, which is why deep recursion runs out of room.

Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18
Page: https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e

## Ready when they can

- Write a recursive function with a base case and a case that shrinks the input
- Trace the call stack for a small input and say which call returns first
- Rewrite a simple loop as recursion, and say what a missing base case causes

## Lesson: Functions that call themselves

A recursive function solves a problem by calling itself on a smaller version of the same problem. You always give it a base case, a tiny input it answers directly, and every other call must shrink the input toward that base.

**Example.** Follow factorial: 0 factorial and 1 factorial both equal 1, and for bigger n, n factorial is n times n minus 1 factorial. To find 5 factorial you wait through 4, 3 and 2 factorial down to the base, then multiply back up to 120. Adding down works the same: sum to 3 is 3 plus 2 plus 1 plus 0, which is 6.

Every call that has not returned yet waits on the call stack. You push a frame per call and pop it on return, so the deepest call finishes first. Without a base case the calls never stop and the stack runs out of room. The palindrome check shows the same shape: compare the outer letters, then recurse on the middle until 1 letter or none remains, as level shrinks to eve and then to v.

**Tip.** You rewrite a loop as recursion by naming its stop as the base and its step as the shrink. A loop adding 1 to n becomes a base of 0 returning 0 plus n added to the call on n minus 1. If the input never shrinks, the base stays out of reach.

**Recap.** Shrink each call toward a base case, and the stack unwinds from the deepest call upward.

## Practice

18 questions on this page, each with its working shown.

## Needs first

- [Stacks: Last In, First Out](https://lightmysky.com/learn/computing/stacks-last-in-first-out-mt_Evw7zeJE6Q)
- [Return Values and Variable Scope](https://lightmysky.com/learn/computing/return-values-and-variable-scope-mt_jivtTHpZc7)

## Opens up

- [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8)
- [The Halting Problem: A Task No Program Can Do](https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr)
- [Merge Sort and Divide and Conquer](https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l)