C 语言递归类型

17 Mar 2025 | 5 分钟阅读

本节将讨论C编程语言中不同类型的递归。递归是一个函数调用自身多达n次的过程。如果一个程序允许用户在同一函数内递归地调用一个函数，这个过程就称为函数的递归调用。此外，一个递归函数可以在同一个程序中直接或间接地调用自己。

递归函数的语法

void recursion ()
{
recursion(); // The recursive function calls itself inside the same function
}
int main ()
{
recursion (); // function call
}

在上面的语法中，main() 函数只调用一次递归函数。之后，递归函数会根据定义的条件调用自身，如果用户没有定义条件，它会无限次地调用同一函数。

不同类型的递归

以下是C编程语言中递归的类型：

直接递归
间接递归
尾递归
非尾/头递归
线性递归
树递归

直接递归

当一个函数在同一个函数内重复调用自己时，这被称为直接递归。

直接递归的结构

fun()
{
// write some code
fun();
// some code
}

在上面的直接递归结构中，外部的 fun() 函数递归地调用内部的 fun() 函数，这种类型的递归被称为直接递归。

让我们编写一个程序来演示C编程语言中的直接递归。

Program2.c

#include<stdio.h>
int fibo_num (int i)
{
// if the num i is equal to 0, return 0;
if ( i == 0)
{
return 0;
}
if ( i == 1)
{
return 1;
}
return fibo_num (i - 1) + fibonacci (i -2);
}
int main ()
{
int i;
// use for loop to get the first 10 fibonacci series
for ( i = 0; i < 10; i++)
{
printf (" %d \t ", fibo_num (i));
}
return 0;
}

输出

0	1	1	2	3	5	8	13	21	34

间接递归

当一个函数被另一个函数以循环方式相互调用时，该函数被称为间接递归函数。

间接递归的结构

fun1()
{
//  write some code 
fun2()
}
fun2()
{
// write some code
fun3()
// write some code
}
fun3()
{
// write some code
fun1()
}

在这个结构中，有四个函数：fun1()、fun2()、fun3()和fun4()。当fun1()函数执行时，它会调用fun2()来执行。然后，fun2()函数开始执行并调用fun3()函数。通过这种方式，每个函数都会引导到另一个函数，使它们的执行形成一个循环。这种方法被称为间接递归。

让我们编写一个程序来演示C编程语言中的间接递归。

Program3.c

#include <stdio.h>
// declaration of the odd and even() function
void odd(); // Add 1 when the function is odd() 
void even(); // Subtract 1 when the function is even
int num = 1; // global variable 
void odd ()
{   
    // if statement check and execute the block till n is less than equal to 10
	if (num <= 10)
	{
		printf (" %d ", num + 1);  // print a number by adding 1
		num++; // increment by 1
		even(); // invoke the even function
	}
	return;
}
void even ()
{
	// if block check the condition that n is less than equal to 10
	if ( num <= 10)
	{
		printf (" %d ", num - 1); // print a number by subtracting 1 
		num++;
		odd(); // call the odd() function
	}
	return;
}
int main ()
{
	odd(); // main call the odd() function at once
	return 0;
}

输出

2  1  4  3  6  5  8  7  10  9

尾递归

如果一个函数进行递归调用，并且该递归调用是函数执行的最后一条语句，那么这个递归函数就称为尾递归。之后，没有其他函数或语句需要调用该递归函数。

让我们编写一个程序来演示C编程语言中的尾递归。

Program4.c

#include <stdio.h>
// function definition
void fun1( int num)
{
	// if block check the condition
	if (num == 0)
		return;
	else
		printf ("\n Number is: %d", num); // print the number
	return fun1 (num - 1);		// recursive call at the end in the fun() function 
}
int main ()
{
	fun1(7); // pass 7 as integer argument
	return 0;
}

输出

Number is: 7
 Number is: 6
 Number is: 5
 Number is: 4
 Number is: 3
 Number is: 2
 Number is: 1

非尾/头递归

如果一个函数进行递归调用，并且该递归调用是函数中的第一条语句，那么这个函数就称为非尾递归或头递归。这意味着在递归调用之前不应有任何语句或操作。此外，头递归在递归调用时不执行任何操作，所有操作都在返回时完成。

让我们编写一个程序来演示C编程语言中的头/非尾递归。

Program5.c

#include <stdio.h>
void head_fun (int num)
{
if ( num > 0 )
{
// Here the head_fun() is the first statement to be called
head_fun (num -1);
printf (" %d", num);
}
}
int main ()
{
int a = 5;
printf (" Use of Non-Tail/Head Recursive function \n");
head_fun (a); // function calling
return 0;
}

输出

Use of Non-Tail/Head Recursive function
 1 2 3 4 5

线性递归

如果一个函数在每次运行时只对自己进行一次调用，并且其增长与问题的大小成线性比例，那么这个函数就称为线性递归。

让我们编写一个程序来演示C编程语言中的线性递归。

Program6.c

#include <stdio.h>
#define NUM 7
int rec_num( int *arr, int n)
{
	if (n == 1)
	{
		return arr[0];
		}	
	return Max_num (rec_num (arr, n-1), arr[n-1]);	
}
// get the maximum number
int Max_num (int n, int m)
{
	if (n > m)
		return n;
	return m;
}
int main ()
{
	// declare and initialize an array
	int arr[NUM] = { 4, 8, 23, 19, 5, 35, 2};
	int max = rec_num(arr, NUM); // call function
	printf (" The maximum number is: %d\n", max); // print the largest number
}

输出

The maximum number is: 35

树递归

如果一个函数在递归函数内部对自己进行一次以上的调用，那么这个函数就称为树形递归。

让我们编写一个程序来演示C编程语言中的树形递归。

Program7.c

#include <stdio.h>
// It is called multiple times inside the fibo_num function
int fibo_num (int num)
{
if (num <= 1)
	return num;
return fibo_num (num - 1 ) + fibo_num(num - 2);
}
void main()
{
int num = 7;
printf (" Use of Tree Recursion: \n");
// print the number
printf (" The Fibonacci number is: %d", fibo_num(7));
}

输出

Use of Tree Recursion:
 The Fibonacci number is: 13

下一主题在C语言中将大写字母转换为小写字母

C 语言递归类型

不同类型的递归

直接递归

间接递归

尾递归

非尾/头递归

线性递归

树递归

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言递归类型

不同类型的递归

直接递归

间接递归

尾递归

非尾/头递归

线性递归

树递归

相关帖子

C 语言全局变量

C 语言函数间通信

C 语言字符串连接

C 语言 Fabs() 函数

C 语言求二次方程根的程序

C 语言交换数字的首位和末位

C 语言中如何相加矩阵

C 语言中的强数

基础 C 程序

C 语言入口控制循环

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器