**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Recursive definition

Summary

In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff). Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set.
A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function n! is defined by the rules
:\begin{align}
& 0! = 1. \
& (n+1)! = (n+1) \cdot n!.
\end{align}
This definition is valid for each natural number n, because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure for computing the value of the function n!, starting from n = 0 and proceeding onwards with n = 1, 2, 3 etc.
The recursion theorem states that such a definition indeed defines a

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (1)

Related people

Related units

No results

No results

Loading

Martin Odersky, Matthias Zenger

Join calculus, usually presented as a process calculus, is suitable as a foundation of both sequential and concurrent programming. We give a new operational semantics of join calculus, expressed as a reduction system with a single reduction rule similar to beta reduction in lambda calculus. We also introduce a new Hindley/Milner style type system for join calculus. Compared to previous work, the type system gives more accurate types of composite and mutually recursive definitions. The type system's soundness is established by showing that our reduction rule keeps typings invariant. We present an algorithm for type inference and show its soundness and completeness.

1999Related concepts (8)

Mathematical logic

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research i

Function (mathematics)

In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the dom

Exponentiation

In mathematics, exponentiation is an operation involving two numbers, the base and the exponent or power. Exponentiation is written as bn, where b is the base and n is the

Related courses (8)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

CS-210: Functional programming

Understanding of the principles and applications of functional programming, the fundamental models of program
execution, application of fundamental methods of program composition, meta-programming through the construction of
interpreters and advanced programming techniques.

CS-452: Foundations of software

The course introduces the foundations on which programs and programming languages are built. It introduces syntax, types and semantics as building blocks that together define the properties of a program part or a language. Students will learn how to apply these concepts in their reasoning.

Related lectures (21)