如何学习递归

dinghuang

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

FishC

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

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

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

def factorial(n):
       if n == 1:
           return 1
       else:
           return n * factorial(n-1)

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

def fibonacci(n):
       if n <= 0:
           return 0
       elif n == 1:
           return 1
       else:
           return fibonacci(n-1) + fibonacci(n-2)

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

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

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

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

def list_sum(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + list_sum(lst[1:])

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

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

某一个“天”

duoxueduolian
多学多练

柿子饼同学

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

jackz007

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

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

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

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

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

#include <stdio.h>

void foo(char s[] , int n)
{
        if(s[n]) {
                printf("%c" , s[n])                        ; // 【进入过程】正序打印字符串
                foo(s , n + 1)                             ;
                printf("%c" , s[n])                        ; // 【退出过程】逆序打印字符串
        } else {
                printf("\n【递归终点】\n")                 ;
        }
}

int main(void)
{
        char a[] = "I'm a chinese, I love my motherland !" ;
        foo(a , 0)                                         ;
        printf("\n")                                       ;
}

        编译运行实况：

D:\[exercise]\C>g++ -o x x.c

D:\[exercise]\C>x
I'm a chinese, I love my motherland !
【递归终点】
! dnalrehtom ym evol I ,esenihc a m'I

D:\[exercise]\C>

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

#include <stdio.h>

int main(void)
{
        char s[] = "I'm a chinese, I love my motherland !" ;
        int n                                              ;
        for(n = 0 ; s[n] ; n ++) printf("%c" , s[n])       ;
        n --                                               ;
        printf("\n【递归终点】\n")                         ;
        for(; n >= 0 ; n --) printf("%c" , s[n])           ;
        printf("\n")                                       ;
}

豆嘉木

你可以认为，递归就是

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

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

dinghuang

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

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

好的，谢谢

峥途

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

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