递归相关的的两道面试题

腾讯面试题：50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？

分析题目：

到第一层只有一种情况上一阶即可即为1

到第二层有两种情况11和2

到第三层有111、12、21三种情况

到第四层有1111、121、112、22、211吴种情况

...

要到第50层要么从48层上两阶到达或者从49层上一阶到达

f(50)=f(49)+f(48)

同理：f(49)=f(48)+f(47)

归纳得通式

f(n)=f(n-1)+f(n-2) (n>=2)

解决递归：

1.找出递归终止的条件

2.找出递归关系式

#include<stdio.h>
#include<stdlib.h>
double calc_upstairs_recursion(int n) //值比较大所以使用double
{
	if(n==1)//找出递归终止条件
	{
		return 1;
	}
	else if(n ==2)
	{
		return 2;
	}
	else
	{
		return calc_upstairs_recursion(n-1)+calc_upstairs_recursion(n-2);//找出递归关系条件
	}
}
double calc_upstairs_loop(int n)
{
	double *tmp =NULL;
	double sum = 0;
	int i;
	if(n<=2)
	{
		return n;
	}
	tmp =(double *)malloc(sizeof(double)*n);
	tmp[0]= 1;
	tmp[1] = 2;
	for( i=2;i<n;i++)
	{
		tmp[i] = tmp[i-1] +tmp[i-2];
	}
	sum = tmp[n-1];
	free(tmp);
	return sum;
}
void main()
{
	printf("使用循环：%f",calc_upstairs_loop(30));
	printf("使用递归：%f",calc_upstairs_recursion(30));
	system("pause");
}
           

2.给定个数组：int a[10]= {1,2,3,4,5,6,7,8,9,10};使用递归来判断数组a是否为递增序列？

1.找出递归终止的条件

2.找出递归关系式

#include<stdio.h>
#include<stdlib.h>

int is_increase(int start_pos,int length,int *pdata)
{
    if(start_pos==length-2) //递归结束的条件
    {
        return pdata[start_pos+1]>pdata[start_pos];
    
    }

    return pdata[start_pos+1]>pdata[start_pos]&&is_increase(start_pos+1,length,pdata);//递归关系
}


void main()
{
    int a[10]= {1,2,3,4,5,6,7,8,9,10};
    int res=is_increase(0,10,a);
    if(res ==1)
    {
        printf("是递增的\n");
    }
    else
    {
        printf("不是递增的\n");
    }

    system("pause");
}
}
           

3 总结：

 究竟什么样的问题适合使用递归来求解？

1.一个问题可以被分解成为若干个子问题

2.子问题除了数据规模不一样，求解思路完全一样

3.存在递归终止条件

编写递归代码关键是：找到递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

使用递归的带来问题：

堆栈溢出、重复计算等。