Descent function

A descent function is in the mathematics and in the computer science a function can be demonstrated with that a recursion terminates.

principle

A descending function is defined for a recursive function , the value of which decreases with each call of . This is chosen for the sake of simplicity . Such a descent function can be chosen, for example, so that it indicates the number of recursion steps remaining until the recursion terminates. Instead of the relation <(is smaller than) in , however, any other well-founded relation in can be used, i.e. every relation in that establishes an order in every subset of that begins with a certain element of this subset. ${\displaystyle f\colon A\to B}$ ${\displaystyle g\colon A\to D}$ ${\displaystyle f}$ ${\displaystyle D=\mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$

It is now demonstrated that the value of decreases with each call of , that is, if the value of is necessary for the calculation of , must apply. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f(x)}$ ${\displaystyle f(x')}$ ${\displaystyle g(x')<g(x)}$

The condition that the relation <must be well founded means that there must be a minimum. So at some point there cannot be a value of for which a smaller value can be found. From the fact that, according to the definition of , the value of must decrease with each recursion step, it can now be deduced that from any value onwards no further recursion step takes place and thus that the recursion terminates. ${\displaystyle g(x)}$ ${\displaystyle g(x')}$ ${\displaystyle g}$ ${\displaystyle x}$

Examples

mathematics

Be

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} ,x\mapsto f(x)={\begin{cases}f(x-1)+x,&{\mbox{wenn }}x>13\\0&{\mbox{sonst}}\end{cases}}}$

We define the descent function as follows:

${\displaystyle g\colon \mathbb {Z} \to \mathbb {N} ,x\mapsto g(x)=x-13}$

With according to recursive function definition

${\displaystyle x'=x-1}$

is

${\displaystyle {\begin{matrix}g(x')&<&g(x)\\g(x-1)&<&g(x)\end{matrix}}}$

and thus

${\displaystyle {\begin{matrix}(x-1)-13&<&x-13\\-14&<&-13\end{matrix}}}$

true. This shows that the value of decreases with each recursion step; but since it cannot sink indefinitely, the recursion terminates. ${\displaystyle g(x)}$ ${\displaystyle \mathbb {N} }$

Computer science

An algorithm is given by the following Java code :

 void triangle(String s) {
     System.out.println(s);
     if(s.length() <= 1) return;
     triangle(s.substring(1));
 }

So here the function triangle is called with a character string as argument. The transferred text is output, then the method is exited if the length of the string is only one character or less. However, if it is larger, the triangle method is called recursively with the rest of the character string after the first character has been truncated. A call with the string "Hello!" so results in the following output:

Hallo!
allo!
llo!
lo!
o!
!

To prove that triangle doesn't just say "Hello!" terminated, but also for all others, we use the length of the character string as the descent function . The result of the truncation of the first character in the recursion is ${\displaystyle s}$

${\displaystyle g\colon \mathbb {N} \to \mathbb {N} ,length_{s}\mapsto g(length_{s})=length_{s}-1}$

And so also about

${\displaystyle {\begin{matrix}g(laenge_{s}')&<&g(laenge_{s})\\length_{s}-1&<&length_{s}\\1&>&0\end{matrix}}}$

and the definition of the soundness that the recursion terminates.

See also

• Well-founded quantity , order and order relation