C语言之递归

ops/2025/2/25 2:59:49/

前言

一、递归原理

二、栈溢出

三、案例

1、两个整数的最大公约数

2、裴波那契序列

3、汉诺塔

4、判断是否为回文数

总结

前言

递归在计算机科学中是一个重要的概念，它指的是一个函数直接或间接地调用自身的过程。在C语言中，递归通常用于解决问题的分治或分解，将一个大问题拆分成较小的同类问题来解决。递归函数必须包含一个递归出口，即递归调用的条件，否则会导致无限循环而造成栈溢出。

一、递归原理

二、栈溢出

无终止条件会产生栈溢出的情况

#include <stdio.h>
int fun01(int n);
int main ()
{printf("%d\n",fun01(5));return 0;
}int fun01(int n)
{/*if (n==1){return 1;}*/return n*fun01(n-1);
}

三、案例

1、两个整数的最大公约数

#include <stdio.h>
int fun11(int m,int n);
int main ()
{/* 递归实现：两个正整数的最大公约数 */printf("%d\n",fun11(124,36 ));return 0;
}int fun11(int m,int n)
{if (m % n == 0)return n;return fun11(n,m%n);
}

2、裴波那契序列

知道前两项的初始值作为递归结束条件，后一个数等于前两个数之和需要用递归调用得到。

#include <stdio.h>
int fun13(int n);
int main ()
{/*用递归算法实现斐波那契数列： */int i;for(i=1;i<=20;i++){printf("%d,",fun13(i));}return 0;
}
int fun13(int n)
{if (n==1||n==2){return 1;}return fun13(n-1)+fun13(n-2);
}

3、汉诺塔

#include <stdio.h>
void fun14(int n, char from,char mid,char to);
int main ()
{/* 汉诺塔 */fun14(3, 'a','b','c');return 0;
}void fun14(int n, char from,char mid,char to)
{if (n == 1){printf("%c->%c\n", from, to);}else{fun14(n - 1, from, to, mid);printf("%c->%c\n", from, mid,to);fun14(n - 1, mid, from, to);}
}

4、判断是否为回文数

#include <stdio.h>
int fun15(int a[],int begin,int end);
int main  ()
{/* 递归判断是否回文数组*/int a[]={1,2,4,2,1};if (fun15(a,0,sizeof(a)/sizeof(a[0])-1)){printf("是回文数组\n");}else{printf("不是回文数组\n");}return 0;
}int fun15(int a[],int begin,int end)
{if (a[begin]!=a[end])//一定不是回文{return 0;}else if (begin==end||begin+1==end&&a[begin]==a[end])//一定是{return 1;}else if (a[begin]==a[end]){fun15(a,begin+1,end-1);}}