/prog/ - Recursion — Tinychan BBS

Name: Anonymous 2013-09-06 8:28

When to use recursion? What is the cue when you have to use recursion?

Suppose I am to write a program that computes a factorial or checks if a string is a palindrome or prints all numbers from a certain range? I could use loops for those but I could use recursion?

What's the advantage of either? Is there something that recursion could do that loops could not?

Name: Anonymous 2013-09-06 8:34

recursion is just neat tricks that go down the toilet when you stack overflow (which happens in all but a few lisp dialects)

Name: Anonymous 2013-09-06 8:46

Recursion makes solutions far cleaner at times. More easily dynamic. With tail-recursion, which is supported by most compilers nowdays, and in things like Scheme, there's no penalty due to stack overflows or function calls.

Name: Anonymous 2013-09-06 8:57

>>3
this crashes here

int rec(int i){
    return rec(i);   
}

int main(){
    rec(1);   
}

Name: Anonymous 2013-09-06 9:06

Recursion is required to deal with nested structures, such as trees. Furthermore, functional programming language fetishists have a strong dislike for loops because they require state management (temporary loop variable) and thus will always consider recursion cleaner.

Name: Anonymous 2013-09-06 9:12

>>4
It is optimized away, for me:

--> cat rectest.c
int rec(int i){
        return rec(i);
}

int main(){
        rec(1);
}

--> clang -O3 rectest.c -o rec; ./rec
-->

Changing it to:

#include <stdio.h>
int rec(int i){
        putchar((i%26)+'a');
        return rec(i+1);
}

int main(){
        rec(1);
}

It never terminates:

--> time ./rec > /dev/null                               
^C
./rec > /dev/null  29.45s user 0.08s system 99% cpu 29.598 total

Here's the generated ASM, it even labels the tail recursion:

 40 main:                                   # @main
 41 .Leh_func_begin1:
 42 # BB#0:
 43   pushq %rbp
 44 .Ltmp4:
 45   movq  %rsp, %rbp
 46 .Ltmp5:
 47   pushq %rbx
 48   pushq %rax
 49 .Ltmp6:
 50   movl  $1, %ebx
 51   .align  16, 0x90
 52 .LBB1_1:                                # %tailrecurse.i
 53                                         # =>This Inner Loop Header: Depth=1
 54   movslq  %ebx, %rbx
 55   imulq $1321528399, %rbx, %rax # imm = 0x4EC4EC4F
 56   movq  %rax, %rcx
 57   shrq  $63, %rcx
 58   sarq  $35, %rax
 59   addl  %ecx, %eax
 60   imull $26, %eax, %eax
 61   movq  stdout(%rip), %rsi
 62   negl  %eax
 63   leal  97(%rbx,%rax), %edi
 64   callq _IO_putc
 65   incl  %ebx
 66   jmp .LBB1_1
 67 .Ltmp7:
 68   .size main, .Ltmp7-main
 69 .Leh_func_end1:

Name: >>6 2013-09-06 9:15

Oh, sorry, didn't copy the whole thing:

  6 rec:                                    # @rec
  7 .Leh_func_begin0:
  8 # BB#0:
  9   pushq %rbp
 10 .Ltmp0:
 11   movq  %rsp, %rbp
 12 .Ltmp1:
 13   pushq %rbx
 14   pushq %rax
 15 .Ltmp2:
 16   movl  %edi, %ebx
 17   .align  16, 0x90
 18 .LBB0_1:                                # %tailrecurse
 19                                         # =>This Inner Loop Header: Depth=1
 20   movslq  %ebx, %rbx
 21   imulq $1321528399, %rbx, %rax # imm = 0x4EC4EC4F
 22   movq  %rax, %rcx
 23   shrq  $63, %rcx
 24   sarq  $35, %rax
 25   addl  %ecx, %eax
 26   imull $26, %eax, %eax
 27   movq  stdout(%rip), %rsi
 28   negl  %eax
 29   leal  97(%rbx,%rax), %edi
 30   callq _IO_putc
 31   incl  %ebx
 32   jmp .LBB0_1
 33 .Ltmp3:
 34   .size rec, .Ltmp3-rec
 35 .Leh_func_end0:
 36 
 37   .globl  main
 38   .align  16, 0x90
 39   .type main,@function
 40 main:                                   # @main
 41 .Leh_func_begin1:
 42 # BB#0:
 43   pushq %rbp
 44 .Ltmp4:
 45   movq  %rsp, %rbp
 46 .Ltmp5:
 47   pushq %rbx
 48   pushq %rax
 49 .Ltmp6:
 50   movl  $1, %ebx
 51   .align  16, 0x90
 52 .LBB1_1:                                # %tailrecurse.i
 53                                         # =>This Inner Loop Header: Depth=1
 54   movslq  %ebx, %rbx
 55   imulq $1321528399, %rbx, %rax # imm = 0x4EC4EC4F
 56   movq  %rax, %rcx
 57   shrq  $63, %rcx
 58   sarq  $35, %rax
 59   addl  %ecx, %eax
 60   imull $26, %eax, %eax
 61   movq  stdout(%rip), %rsi
 62   negl  %eax
 63   leal  97(%rbx,%rax), %edi
 64   callq _IO_putc
 65   incl  %ebx
 66   jmp .LBB1_1
 67 .Ltmp7:
 68   .size main, .Ltmp7-main
 69 .Leh_func_end1:

Name: >>7 2013-09-06 9:23

Ah, looks like the code segment was the same either way. I suppose it inlined the function as well. Either way, it becomes a non-conditional jmp to after the function entry so the stack isn't touched.

Making it simpler, without libc calls:

extern n(int i);
int rec(int i){
        n(i);
        return rec(i+1);
}

int main(){
        rec(1);
}

ASM:

  6 rec:                                    # @rec
  7 .Leh_func_begin0:
  8 # BB#0:
  9   pushq %rbp
 10 .Ltmp0:
 11   movq  %rsp, %rbp
 12 .Ltmp1:
 13   pushq %rbx
 14   pushq %rax
 15 .Ltmp2:
 16   movl  %edi, %ebx
 17   .align  16, 0x90
 18 .LBB0_1:                                # %tailrecurse
 19                                         # =>This Inner Loop Header: Depth=1
 20   movl  %ebx, %edi
 21   callq n
 22   incl  %ebx
 23   jmp .LBB0_1

Lines 18-23 just move set the register for the call, call the function, increment ebx, and then jump back to copying the register for the call.

Just have to use an -O switch.

Name: Anonymous 2013-09-06 10:11

>>5

What if I'm not a functional programmer?

Name: Anonymous 2013-09-06 10:13

>>9
Then you should only use recursion for recursive data structures and when a recursive function is shorter than the respective loop (assuming you don't need a break statement).

Name: Anonymous 2013-09-06 11:00

>>10

when a recursive function is shorter than the respective loop

Then that would be almost always.

Name: Anonymous 2013-09-06 14:34

>>11
Give examples, please

Name: can't hold all these inepts 2013-09-06 18:08

>>1,12
https://www.google.com/search?q=when+to+use+recursion

About 5,760,000 results (0.24 seconds)

Name: Anonymous 2013-09-07 11:18

There's a function call overhead in a lot of programming languages so recursion is worse than iteration

Name: Anonymous 2013-09-07 12:17

If your language supports tail call recursion, recursion can be pretty useful. Once you start doing anything at scale though, recursion falls apart. You'd probably want to try trampolining instead.

Name: Anonymous 2013-09-07 12:55

Been a while since I've had to look into it, but don't the fastest sorting algorithms still use recursion?

Name: Anonymous 2013-09-07 13:24

>>16
FIBONACCI BUTT SORT

Name: Anonymous 2013-09-07 13:44

>>17
U MENA FIBONACCI BUTT SORT

Name: Anonymous 2013-09-07 14:27

λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ

Name: Anonymous 2013-09-07 20:44

>>19

λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ^{λλ^{λλ^{λλλ^{λλλλ^{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ_{λλ_{λλ_{λλλ_{λλλλ_{λλλλλλλλ}λλλλ}λλλ}λλ}λλ}λ

Name: Anonymous 2013-09-07 21:58

>>19,20

     ────┐               ┌────────────┐
         └─────┐       ┌─┘            └──┐           HAVE YOU READ
               └───────┘          ┌───┐  └──┐      YOUR SICP TODAY ?
                                  │ P │     │
                                  └───┘     │
                                            │
                                    ┌───────┘
        ──────────────────┐         └──────┐
                          └─────┐      ┌───┘
                                └──────┘

Name: Anonymous 2013-09-07 23:51

>>21
make a L-system fractal of sicp snake

Recursion

1 Name: Anonymous 2013-09-06 8:28

2 Name: Anonymous 2013-09-06 8:34

3 Name: Anonymous 2013-09-06 8:46

4 Name: Anonymous 2013-09-06 8:57

5 Name: Anonymous 2013-09-06 9:06

6 Name: Anonymous 2013-09-06 9:12

7 Name: >>6 2013-09-06 9:15

8 Name: >>7 2013-09-06 9:23

9 Name: Anonymous 2013-09-06 10:11

10 Name: Anonymous 2013-09-06 10:13

11 Name: Anonymous 2013-09-06 11:00

12 Name: Anonymous 2013-09-06 14:34

13 Name: can't hold all these inepts 2013-09-06 18:08

14 Name: Anonymous 2013-09-07 11:18

15 Name: Anonymous 2013-09-07 12:17

16 Name: Anonymous 2013-09-07 12:55

17 Name: Anonymous 2013-09-07 13:24

18 Name: Anonymous 2013-09-07 13:44

19 Name: Anonymous 2013-09-07 14:27

20 Name: Anonymous 2013-09-07 20:44

21 Name: Anonymous 2013-09-07 21:58

22 Name: Anonymous 2013-09-07 23:51