如何学习递归

dinghuang

递归函数如何理解？遇到题目如何灵活运用？有没有人能教教我

FishC

你好！学习递归可以从以下几个方面入手：

1. **理解递归的基本概念**：
   - 递归函数是一个在函数内部调用自身的函数。
   - 递归的核心是“基准情形”和“递归情形”。基准情形用于结束递归，递归情形则是函数调用自身的部分。

2. **经典递归例子**：
   - **阶乘**：`n! = n * (n-1)!`
  

1. def factorial(n):
   
2.        if n == 1:
   
3.            return 1
   
4.        else:
   
5.            return n * factorial(n-1)

复制代码

   - **斐波那契数列**：`Fib(n) = Fib(n-1) + Fib(n-2)`
  

1. def fibonacci(n):
   
2.        if n <= 0:
   
3.            return 0
   
4.        elif n == 1:
   
5.            return 1
   
6.        else:
   
7.            return fibonacci(n-1) + fibonacci(n-2)

复制代码

3. **理解递归调用栈**：
   - 每一次函数调用时，计算机会将当前状态（参数、返回地址等）保存到调用栈上。
   - 每当基准情形满足时，返回结果，然后逐层返回，最后得到答案。

4. **练习和调试**：
   - 尽量多写一些简单的递归算法，并使用调试工具（如Pycharm中的调试器）一步步跟踪递归调用过程。
   - 画图也可以帮助理解递归每一步的执行流程。

5. **遇到问题的策略**：
   - 识别问题的基本情形。
   - 找出问题如何通过缩小规模的相同问题来解决。
   - 写出递归的关系式并实现函数。

举个例子，计算一个列表的和：

1. def list_sum(lst):
   
2.     if len(lst) == 0:
   
3.         return 0
   
4.     else:
   
5.         return lst[0] + list_sum(lst[1:])

复制代码

希望这些方法能帮助你理解递归，更好地掌握和应用递归！有什么具体的例子或问题也可以继续问，我会尽力帮你解答！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

duoxueduolian
多学多练

柿子饼同学

你可以用模拟栈理解
也可以画一个递归树

jackz007

    1、一个函数调用自己，或者，多个函数彼此相互调用，形成闭环的，都是递归（A->B->C->D->A），其中，前者比较常见；

    2、递归函数必须设置结束条件，并相应设置继续递归和结束递归两个分支；

    3、递归有深度限制，递归过深会导致调用栈耗尽而出错；

    4、递归与循环功能相似，相比之下，递归的效率显著低于循环，递归更适用于循环次数不可预知的情形；

    考察下面的代码，以便加深理解：

1. #include <stdio.h>
   
2. 
   
3. void foo(char s[] , int n)
   
4. {
   
5.         if(s[n]) {
   
6.                 printf("%c" , s[n])                        ; // 【进入过程】正序打印字符串
   
7.                 foo(s , n + 1)                             ;
   
8.                 printf("%c" , s[n])                        ; // 【退出过程】逆序打印字符串
   
9.         } else {
   
10.                 printf("\n【递归终点】\n")                 ;
    
11.         }
    
12. }
    
13. 
    
14. int main(void)
    
15. {
    
16.         char a[] = "I'm a chinese, I love my motherland !" ;
    
17.         foo(a , 0)                                         ;
    
18.         printf("\n")                                       ;
    
19. }

复制代码

        编译运行实况：

1. D:\[exercise]\C>g++ -o x x.c
   
2. 
   
3. D:\[exercise]\C>x
   
4. I'm a chinese, I love my motherland !
   
5. 【递归终点】
   
6. ! dnalrehtom ym evol I ,esenihc a m'I
   
7. 
   
8. D:\[exercise]\C>

复制代码

       用循环替换递归的代码版本是这样的：

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         char s[] = "I'm a chinese, I love my motherland !" ;
   
6.         int n                                              ;
   
7.         for(n = 0 ; s[n] ; n ++) printf("%c" , s[n])       ;
   
8.         n --                                               ;
   
9.         printf("\n【递归终点】\n")                         ;
   
10.         for(; n >= 0 ; n --) printf("%c" , s[n])           ;
    
11.         printf("\n")                                       ;
    
12. }

复制代码

豆嘉木

你可以认为，递归就是

1. while(处理完所有状态):
   
2.         针对上一个状态处理下一个状态

复制代码

所有递归都能写成函数，从实用角度上来说递归还浪费了不少内存空间
但是在算法竞赛里递归可以使代码更具可读性，更好写
建议你去学习一下图论相关知识，比如最简单的dfs (深搜)
然后想练的话去洛谷筛一点递归题
多练练就熟练了

dinghuang

豆嘉木 发表于 2024-10-4 09:41
你可以认为，递归就是

所有递归都能写成函数，从实用角度上来说递归还浪费了不少内存空间

好的，谢谢

峥途

理解递归的关键在于:
1识别问题的递归结构，
2.定义好基本情况和递归情况，
3.并确保递归能够正确终止。

多多掌握如斐波那契数列的经典递归与示例，看前辈们的代码，弄懂，练习一些习题，就能更快的掌握递归，活学活用。