English
Menu

What is Recursion?

A function calling itself as part of its own processing. The problem is split into smaller problems of the same form, and the calls stop at a case that is not split further (the base case). Each call uses stack space, so recursion that is too deep overflows the stack. Tail recursion, where the recursive call is the last thing the function does, can be converted into a loop.

Japanese name: 再帰

Recursion appears in 8 practice questions across 6 topics, including Linkers, Loaders & Executables, Data Structures and Algorithms, CPUs and architecture.

Field: Data Structures and Algorithms

Try it: questions about Recursion

When recursion goes so deep that it exceeds the stack limit, what generally happens on Linux and similar systems?

  1. AIt touches a guard page beyond the stack where access is forbidden, and the program crashes
  2. BThe OS moves the stack to disk automatically, allowing unlimited depth
  3. COld stack frames are deleted automatically and the computation continues correctly
Show answer and explanation

Answer: A. It touches a guard page beyond the stack where access is forbidden, and the program crashes

The stack has a limit, and a guard page with access forbidden sits beyond it. When too-deep recursion pushes the stack into that page, a page fault occurs and the OS stops the program (a segmentation fault). The guard page's advantage is stopping the program before it corrupts other data. A large array as a local variable can cause the same thing, so large data is safer on the heap.

Recursion in the explanations

Questions that mention Recursion (8)

  1. When recursion goes so deep that it exceeds the stack limit, what generally happens on Linux and similar systems?
  2. When a program calls a subroutine (function), which area is generally used to temporarily save the return address and similar information?
  3. What is the effect of applying tail-call optimization to the final recursive call in the function above?
  4. What is the advantage of laying out the heap and stack so they grow in opposite directions with a large gap between them?
  5. On a small microcontroller without an MMU, what should be kept in mind about excessive stack use?
  6. In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?
  7. A function f(x, y) is defined as “if y is 0, return x; otherwise return f(y, x mod y)”. When f(84, 36) is called, what is the return value, and how many times is f called, including the first call?
  8. ÷ is division; when the result is assigned to an integer variable (including a function argument), the fractional part is discarded. When the following function pow is called as pow(2, 10), how many times is pow called, including the first call?

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

Semiconductor, Electronics and Computing Calculators

Pseudocode Runner and TracerRun programs written in the pseudocode of Japan's Fundamental IT Engineer Exam (Part B) and trace each executed line and the values of variables

Related terms

Stack Variable Array Heap memory Argument Return value Page fault Return address Stack pointer Stack frame

Back to the glossary