How do I git gud at recursion? I can't seem to wrap my head around it. I literally have never come up with a function that uses recursion of my own since I started programming.
Recursion
Other urls found in this thread:
geeksforgeeks.org
twitter.com
Start with the base case and move backwards from there.
If you still don't know what recursion is, read this sentence.
try to read nodes of deep structured xml file without using any libraries.
create yourself some functions as this retarded example below
function read_node
read key,value
call function has_child_node
if true call read_node(child_node)
else stop iterating
endfunction
Decompose it into pure functions. And still make it all nice.
Hint, that does not mean you will completely succeed although it is absolutely possible.
I know what it is but I lack the ability to utilize it.
For example, given an array of characters of arbitrary size, print all possible permutations of it. I know recursion is needed somewhere but I can't come up with a way to solve it.
I did some BST traversal before but wouldn't come up with anymore advanced use of recursion of my life depended on it.
Think of it as spliting a question
to a smaller case.
If you have problems understanding what recursion is, there r books u can read to help u understand.
If you have an issue using or dont know when to use solve some sample problems onlinr
Try using a language without for/while.
When you want to do a thing to the result of doing the thing.
to get good at recursion you have to get good at recursion first
Recursion isn't a skill
I have no clue why anyone has trouble with it
If you want to use recursion, traverse a tree or a directory structure or something
If you don't need it, you don't need it
>I literally have never come up with a function that uses recursion of my own since I started programming.
so you're 12?
this. there are data structures that naturally lend themselves to recursive algorithms. if walking a tree in an iterative fashion doesn't give you a bad feeling you're not made for programming
read The Little Schemer, and The Seasoned Schemer
why are functional programmers so pretentious
why are oop programers such weenies
Yeah I admit I actually did some recursion with directories and trees before but they are standard data structures.
I still feel like I know nothing, and that there's a more advanced level of recursion mastery I'll never reach.
Fuck(chars:string,prefix:string="")
if chars.length = 1 then
Print(prefix+chars)
else
for i = 0 until chars.length
Fuck(chars[..i]+chars[i+1..],prefix+chars[i])
end
end
end
traversing trees is all there is to it. There's nothing to "master" about recursion. It's an incredibly simple concept. The above example is basically just treating a string like a tree
>false dichotomy
Use Ocaml or Haskell for a month
Do their 99 problems list. Make sets etc...
what magic language is this? a less retarded ruby?
>Anything that can be done iteratively can be done recursively.
>Recursion blows the stack in most languages that dont use tail-call optimization, and for this it is usually frowned upon by brainlets.
>Recursive languages need a base case to tell them when to end.
>Recursion is similar to proof by induction
>Recursion is best for tree traversals/things with parent child relationship/problems that can be broken down into a smaller version of the same problem
psuedocode
Start with the end step that stops the recursion
I think its definitely something you need to practice with and feel out more. Once you become better at programming recursive solutions will actually become more obvious to you than iterative solutions oddly enough. Anyway try solving a few problems with it.
This is a fun one I think. The goal is to determine if you can end up with 42 bears, but you must follow these rules
(where n is the number of bears that you have):
1. If n is even, then you may give back exactly n/2 bears.
2. If n is divisible by 3 or 4, then you may multiply the last two
digits of n and give back this many bears. (By the way, the last digit
of n is n%10, and the next-to-last digit is ((n%100)/10).
3. If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game is to end up with EXACTLY 42 bears.
Also these look okay
geeksforgeeks.org
Learn Haskell.
>Start with the base case and move backwards from there.
this
>Think of it as spliting a question
>to a smaller case.
this
shit's easy yo. keep a simple example in your head to reason about e.g. reverse(array)
Base: the reverse of [x] is [x], so return it.
Reduce input to subproblem: the reverse of [x,..,y,z] is x + reverse of [y,...,z]
>x + reverse of [y,...,z]
edit: reverse of [y,...,z] + x
I tried, but this still doesn't look like recursion to me
#include
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
void reverse(int arr[], int i, int sz)
{
if (i == sz / 2) return;
swap(&arr[i], &arr[sz-i]);
i--;
reverse(arr, i, sz);
}
void main()
{
int arr[] = {6, 3, 5, 7, 6, 4, 2, 8};
int sz = sizeof(arr) / sizeof(arr[0]) - 1;
reverse(arr, sz, sz);
for (int i = 0; i
doing recursion instead of iteration is a stupid way to learn recursion
you want to do recursion for tasks where iteration isn't suitable
does it work for anyone?
just suppose that you have a function that efficiently solves the problem for any problem size n up to N. try to figure it out how can you move forward efficiently to larger n-s, maybe N+1 or N+2. you are essentially done. for small enough n-s your recursion does not make any sense, these are the base cases. take care of your base cases by using an if function inside your recursive function.
void reverse(...)
{
if (...) return; //base case
...
reverse(...); //recursive case
}
>this still doesn't look like recursion to me
why not
If you disassemble it down to asm this would look exactly the same if you had used a for loop. This is how I write loops in asm.
Learn Scheme or Prolog. I'm not meming. Learning them in uni is what finally made recursion click. You can't do anything in those languages without it, so it forces you to think that way.
Loops and primitive recursion are isomorphic.
What do you mean with "give back"?
look up recursive descending parsing
preferably by using craftinginterpreters